プロジェクトオイラー問78 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2078
Problem 78　「コインの分割」 †
ｎ枚のコインを分割する方法が100万の倍数通りになる最小のｎは幾らか？

解法
Wikiに書いてある分割数の式をそのまま実装します。
１００万の倍数は100万でmodをとって0になれば１００万の倍数です。

#include<stdio.h>
#include<vector>
#include<iostream>

std::vector<__int64> p;
const __int64 MOD=1000*1000;
int main(){
	p.push_back(1);
	p.push_back(1);
	p.push_back(2);
 	for(int i=3;i<100000;i++){
		
		
		__int64 next=0,m=1;
		for(int k=1;;k++){
			int gk=(k*(3*k-1))/2;
			if(i-gk<0)break;
			next=(next+m*p[i-gk])%MOD;
			gk=(-k*(-3*k-1))/2;
 			if(i-gk<0)break;
			next=(next+m*p[i-gk])%MOD;
			m*=-1;
		}
		p.push_back(next);
 		if(next==0){
			printf("ans=%d\n",i);
			break;
		}
	}
}