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

プロジェクトオイラー問７８ - (2014/03/02 (日) 11:17:58) の編集履歴(バックアップ)

---

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