「プロジェクトオイラー問い71～80」の編集履歴（バックアップ）一覧に戻る

---

「プロジェクトオイラー問い71～80」を以下のとおり復元します。

---

*問い71
分母が１００万以下で１より小さい既約分数を小さい順に並べた時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

解法
ファイ関数という概念を知らない時に作った我流ファイテーブル生成コードでアセプト。
車輪の再発明だが自分で考えついたというのがうれしくてつい使ってしまった。
趣味のプログラムだから許されるのであって、プロのプログラマなら専門家や世間が検証済みのアルゴリズムを使う方が正しいよな。
例え天才であっても自前の怪しいコードより世間が検証済みのコードを使うべきと言われるかもしれない。
ましてや凡人の私では世間に従うべきだよな。
まプログラムの仕事なんてものにつけることが出来たらの話か。
うんこのコード、知られてる方法よりメモリを２倍使ってるかな？

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

---

復元してよろしいですか？