「AOJProblem Set from NTL 問0~4」の編集履歴(バックアップ)一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
*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 - 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);
}