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 を求めよ.

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

解法
問76のコードを少しだけ改良して流用します。
計算はmod100万と取った時0になればよいので合同式の中で組み合わせを計算します。

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

const int MOD=1000*1000;

int pos(int n){
      n++;
      int n1=n/2*(n%2==0?1:-1);
      return (n1*(3*n1-1))/2;
}


int main(){
      std::vector<int> dp;
      dp.push_back(1);
      int num=1;
      while(1){
            dp.push_back(0);
            for(int j=1;j<=num;j++){
                  int p=pos(j);
                  if(num-p<0)break;
                  __int64 mult=((j-1)%4)/2==0?1:-1;
                  dp[num]=(dp[num]+dp[num-p]*mult)%MOD;
            }
            if(num>3&&dp[num]==0)break;
            num++;
      }
      std::cout<<num;
}