Elementary Number Theory - Prime Factorize
#include<stdio.h>
int main(){
int n,p=2;
scanf("%d",&n);
printf("%d:",n);
while(n>=p*p){
while(n%p==0){
n/=p;
printf(" %d",p);
}
p+=1+(p&1);
}
if(n>1)printf(" %d",n);
printf("\n");
}
Elementary Number Theory - Power
#include<stdio.h>
#include<iostream>
const long long int MOD=1000000007;
int main(){
long long int n,m,ans=1;
std::cin>>m>>n;
while(n>0){
if(n%2==1){
ans=(ans*m)%MOD;
}
n/=2;
m=(m*m)%MOD;
}
std::cout<<ans<<"\n";
}
Elementary Number Theory - Least Common Multiple
#include<stdio.h>
int gcd ( int a, int b ){
int c;
while ( a != 0 ) {
c = a; a = b%a; b = c;
}
return b;
}
int main(){
int a,b,n;
scanf("%d %d",&n,&a);
for(int i=1;i<n;i++){
scanf("%d",&b);
a*=(b/gcd(a,b));
}
printf("%d\n",a);
}
Elementary Number Theory - Euler's Phi Function
オイラーのファイ関数を実装する問題。
定義通り計算。
よく考えたらint型で十分かな。
#include<stdio.h>
int main(){
int n,p=2,t;
double m;
scanf("%d",&n);
m=t=n;
while(p*p<=n){
if(t%p==0){
m=m*(1.0-1.0/p);
while(t%p==0)t/=p;
}
p+=1+(p&1);
}
if(t>1)m=m*(1.0-1.0/t);
n=m;
printf("%d\n",n);
}
最終更新:2014年01月28日 11:17