Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-05-10

[][] Project Euler Problem 78 23:54 はてなブックマーク -  Project Euler Problem 78 - 練習帳

問題文

 http://projecteuler.net/index.php?section=problems&id=78

要約

 正数 n で,分割数が1,000,000で割り切れるもののうち最小のものを答えよ.

方針

 分割数には漸化式があるので,それをメモ化しつつ計算する*1


コード例(C++)

 正直分割数に漸化式がある事を知りませんでした.母関数とオイラーの五角数定理から証明できるようです.

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

vector<int> table;
int  N = 1000000;

inline int f(int k){return (3 * k * k - k)/2;}
inline int g(int k){return (3 * k * k + k)/2;}

int dp(ll num, bool isprecalced){
  if(num < 0) return 0;
  if(isprecalced) return table[num];
  if(num == 0) return 1;
  int ans = 0;
  int sign = 1;
  for(ll k = 1;; k++){
    int fk = f(k);
    int gk = g(k);
    if(num - fk < 0 && num - gk < 0) break;
    ans =( ( (ans + sign * dp(num - fk,1) + N ) % N )
	   + sign * dp(num - gk,1) + N ) % N ;
    sign *= -1;
  }
  return ans;
}

int main(){  
  for(ll i = 0;; i++){
    int ans = dp(i, 0);
    if(i != 0 && ans == 0){
      cout << i << endl;
      return 0;
    }
    table.push_back(ans);
  }
  return 0;
}

余談

 オイラーの五角数定理はヤコビの三重積公式から証明でき,三重積公式はラマヌジャンの和公式の特殊な場合です.ラマヌジャンの和公式はQ超幾何級数の一つを求める公式で,Q超幾何級数は超幾何級数の「q類似(q analog)」と呼ばれるものです.