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

---

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

---

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2078

*Problem 78　「コインの分割」 †
n 枚のコインを異なった方法で山に分ける場合の数を p(n) と表わす. 例えば, 5枚のコインを山に分ける異なったやり方は７通りなので p(5)=7 となる.

OOOOO

OOOO   O

OOO   OO

OOO   O   O

OO   OO   O

OO   O   O   O

O   O   O   O   O

p(n) が100万で割り切れる場合に最小となる n を求めよ.


 #include<stdio.h>
 #include<vector>
 
 const int MOD=1000*1000;
 int main(){
 	std::vector<int> p;
 	p.push_back(1);
 	p.push_back(1);
 	for(int i=2;;i++){
 		int d=1;
 		int n=1;
  		int add;
 		int sum=0;
 		while(1){
  			int a=(n*(3*n-1))/2;
 			add= i>=a?p[i-a]:0;
 			sum+=add*d;
 			
  			int b=(-n*(3*(-n)-1))/2;
 			add=i>=b?p[i-b]:0;
 			sum=(sum+add*d) % MOD;
 			d*=-1;
 			n++;
 			if(i<b)break;
  		}
 		if(sum==0){
 			printf("%d\n",i);
 			break;
 		}
 		p.push_back(sum);
 	}
 }

---

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