*問い1 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%201 １０００未満で3の倍数又は５の倍数となる自然数の和を求める問題。 プログラムを書くまでもなく数式で一発です。 #include<stdio.h> int main(){ printf("%d",333*167*3+199*100*5-33*67*15); } *問い２ http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%202 フィボナッチ数列のうち４００万以下の偶数となる項の和を求める問題。 解法 フィボナッチ数列は最初奇数、奇数で始まり 奇数+奇数＝偶数 奇数+偶数＝奇数 偶数+奇数＝奇数 奇数+奇数＝偶数 で偶数が３つごとに現れます。 そしてｎ=3k番目のフィボナッチ数列の項を求める関数をf(n)としたとき数式を展開することで f(n)=4*f(n-3)+f(n-6)が常に成り立ちつことが容易に判明します。 後はこれをそのままプログラムにするだけです。 もしかしたらもうひとつ深く考えて行列演算を使えば、ループを行うまでもなく一発で答えが出るかもしれません。 #include<stdio.h> int main(){ int ans=0,y=0,z=2,t; while(z<=400*10000){ t=z*4+y; y=z; z=t; ans+=y; } printf("%d",ans); } *問い３ 3195 の素因数は 5, 7, 13, 29 である. 600851475143 の素因数のうち最大のものを求めよ. 解法 とりあえず試し割をしてみましたが数の特殊性に注目したもう少し賢い方法があるかもしれません。 #include<iostream> int main(){ __int64 num=600851475143L; for(__int64 i=2;i*i<=num;i+=(i&1)+1){ while(num%i==0){ std::cout<<i<<" "; num/=i; } } if(num!=1)std::cout<<num; } *問い4 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%204 左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である. では, 3桁の数の積で表される回文数のうち最大のものを求めよ. 力づくの方法以外をコードをに組み込むとコードが長くなるのでとりやめました。 もし7桁の数同士の掛け算とかとなると難しい。 #include<stdio.h> #include<stdlib.h> #include<string.h> bool isOK(char* str){ int len=strlen(str); for(int i=0;i<len/2;i++){ if(str[i]!=str[len-i-1])return false; } return true; } int main(){ char str[7]; int ans=0; for(int i=100;i<1000;i++){ for(int j=100;j<1000;j++){ int m=i*j; sprintf(str,"%d",m); if(isOK(str)&&ans<m)ans=m; } } printf("%d",ans); } *問い5 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%205 素因数分解の一意性を使って解きます。 1～20まで自然数全ての数で割れる最小の自然数ｍを求めよ。 割る数をｎとした時ｎの素因数をｍが含んでいないといけないということを利用して解きます。 この方法なら、１００までで割れるとかになっても答えを素因数の積で表示できます。 javaのコンテナほど便利でありませんがｃ++のコンテナの便利さを知るとコンテナから離れらないですね。 他の回答者のコードを見ていたら皆LCMで解いてた、確かにこの問題ならそちらの方がコードが短くなる。 言語にLCMが定義されてたら１行で済む場合もあるな、、、 #include<stdio.h> #include<map> #include<math.h> #include<iostream> void calc(int n){ int num; std::map<int,int> anss; for(int i=2;i<=n;i++){ num=i; for(int j=2;j*j<=n;j++){ int count=0; while(num%j==0){ num/=j; count++; } if(count>0){ if(anss.find(j)==anss.end()||anss[j]<count)anss[j]=count; } } if(num!=1){ if(anss.find(num)==anss.end()||anss[num]<1)anss[num]=1; } } int ans=1; for(std::map<int,int>::iterator it=anss.begin();it!=anss.end();it++){ std::cout<<(*it).first<<" "<<(*it).second<<"\n"; ans*=pow((*it).first,(*it).second); } std::cout<<ans; } int main(){ calc(20); } *問い6 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%206 最初の10個の自然数について, その二乗の和は, 12 + 22 + ... + 102 = 385 最初の10個の自然数について, その和の二乗は, (1 + 2 + ... + 10)2 = 3025 これらの数の差は 3025 - 385 = 2640 となる. 同様にして, 最初の100個の自然数について二乗の和と和の二乗の差を求めよ. 解法 プログラムを書くまでもなく数式で一発です。 #include<stdio.h> #include<math.h> int calc(int n){ return (3*pow(n,4)+2*pow(n,3)-3*pow(n,2)-2*n)/12; } int main(){ printf("%d",calc(100)); } *問い7 素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である. 10 001 番目の素数を求めよ. 解法 素数が絡むと問題の難易度が低く設定されやすくなるように思えます。 素数の判定や素数にかかわる性質は複雑で高度なために一般の参加者が知らない性質が増えます。 そのため専門知識がなくても解けるよう試し割程度で片がつく問題が出題されやすくなります。 高度な専門知識がなくても柔軟な発想力で参加できる、これが競技プログラムの良さだと思います。 #include<stdio.h> #include<math.h> bool isPrime(int n){ for(int i=2;i*i<=n;i+=(i&1)+1){ if(n%i==0)return false; } return true; } int main(){ int count=1,ans=3; while(1){ if(isPrime(ans)==true)count++; if(count>=10001)break; ans+=2; } printf("%d",ans); }
