「AOJProblem Set from NTL 問0～4」の編集履歴（バックアップ）一覧に戻る

AOJProblem Set from NTL 問0～4 - (2014/01/28 (火) 11:17:08) のソース

*Elementary Number Theory - Prime Factorize
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_A
素因数を出力する問題
試し割で十分間に合います。

 #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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_B
a^10億乗とかそれくらいの値を10億7で割った数を計算する問題。

 #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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_C&lang=jp
ｎ個の数の最小公倍数を求める問題。
一つずつ計算すれば簡単です。


 #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);
 }