*問い71 分母が100万以下で1より小さい既約分数を小さい順に並べた時3/7の左にある分数の分子を答えよ。 解法 ファーレー数列で一発です。 ファーレー数列が何故既約な分数を生成するかは理屈より図解で勉強したほうが分かりやすいか。 あれ?ファーレース数列の概念を使えばファイ関数が綺麗にもとまるのかな? #include<stdio.h> struct S{ int n,m; S operator+(const S& s){ S re; re.n=n+s.n; re.m=m+s.m; return re; } }; int main(){ S s1,s2,s3; s1.n=2; s1.m=5; s2.n=3; s2.m=7; while(1){ s3=s1+s2; if(s3.m>=1000*1000)break; s1=s3; } printf("%d",s1.n); } *問い72 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2072 解法 ファイ関数という概念を知らない時に作った我流ファイテーブル生成コードでアセプト。 車輪の再発明だが自分で考えついたというのがうれしくてつい使ってしまった。 趣味のプログラムだから許されるのであって、プロのプログラマなら専門家や世間が検証済みのアルゴリズムを使う方が正しいよな。 例え天才であっても自前の怪しいコードより世間が検証済みのコードを使うべきと言われるかもしれない。 ましてや凡人の私では世間に従うべきだよな。 まプログラムの仕事なんてものにつけることが出来たらの話か。 うんこのコード、知られてる方法よりメモリを2倍使ってるかな? #include<stdio.h> #include<iostream> const int up=1000000; int count[up+1]={0}; int dellCount[up+1]={0}; void print(){ for(int i=1;i<=up;i++){ printf("%d ",count[i]); } printf("\n"); } int main(){ for(int i=2;i<=up/2;i++){ if(dellCount[i]==0){ //printf("%d a=",i); int dell=-1; for(int j=i*2;j<=up;j+=i){ count[j]+=dell; dell--; dellCount[j]++; } }else if(dellCount[i]>0){ //printf("%d b=",i); int add=dellCount[i]-1; int base=add; for(int j=i*2;j<=up;j+=i){ count[j]+=base; base+=add; dellCount[j]-=add; } }else{ int add=-dellCount[i]+1; int base=add; for(int j=i*2;j<=up;j+=i){ count[j]+=base; base+=add; dellCount[j]-=add; } } //print(); } __int64 ans=0; for(int i=1;i<=up;i++){ ans+=i+count[i]-1; } std::cout<<ans; }