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
n個の数の最小公倍数を求める問題。
一つずつ計算すれば簡単です。


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

タグ:

+ タグ編集
  • タグ:

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー利用規約 が適用されます。

最終更新:2014年01月28日 11:17