Project Euler Problem 78

解法

分割数 - Wikipediaを参考にして漸化式を作りました．

実装(C++)

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long lli;
const int MOD=1000000;
//五角数を求める
int pentagonal(int i){
	return (i*(3*i-1))/2;
}
int p_memo[1000000];
int partition_function(int k){
	if(k<=1)return 1;
	int ans=0;
	if(p_memo[k]>0)return p_memo[k];
	for(int i=1;;i++){
		for(int j=1;j>=-1;j-=2){
			int p=abs(pentagonal(i*j));
			if(k-p<0)return p_memo[k]=ans%MOD;
			if(i%2==1)ans+=partition_function(k-p);
			else ans-=partition_function(k-p);
			ans=(ans%MOD+MOD)%MOD;
			ans%=MOD;
		}
	}
	return p_memo[k]=MOD;
}
int main() {
	for(int i=1;;i++){
		if(i%1000==0)cout<<i<<endl;
		if(partition_function(i)==0){
			cout<<"Answer:"<<i<<endl;
			break;
		}
	}
	return 0;
}