問題文: Unit Fraction Partition | Aizu Online Judge
汚いソースなんだよね。それ一番言われてるから。
自明な枝狩りをきちんと実装できるかが問題。
また k*(1/current) がp/qより小さい場合枝狩り。
↑とくにこのへん
あとオーバーフローに対する処理を手抜きしている。
#include <iostream> #include <vector> #include <algorithm> #include <map> using namespace std; // 無駄に累乗を高速化している。 int memo[12001][8]; int b_pow(int a,int b){ if(memo[a][b]) return memo[a][b]; else if( b == 0 ) return 1; else if( b == 1 ) return a; else return memo[a][b] = b_pow(a,b/2) * b_pow(a,(b+1)/2); } int ans , A; //余っているやつをp/q , 余っている残り回数をk , 現在までの積を product , 現在見ている1/current 。 int dfs(int p , int q , int k , int product , int current){ // productがoverflowした。(produt <= 0) もしくはAを超えた場合 、また k*(1/current) がp/qより小さい場合枝狩り。 if( product <= 0 || product > A || p*current > k*q ) return 0 ; if( p == 0 ) return 1; if( current*product > A || k == 0 || p == 0) return 0; int ans = 0; // {1/current}を何回使うかを決める for(int i = 0 ; i <= k ; i++){ if(p*current >= i*q) { int bunsi = p * current - i * q; int bunbo = q * current; if(bunsi != 0){ int g = __gcd(bunsi,bunbo); bunsi /= g , bunbo /= g; } ans += dfs(bunsi , bunbo , k - i , product * b_pow(current,i) , current + 1); }else{ break; } } return ans; } int main(){ int a,b,c,d; while(cin >> a >> b >> c >> d , a || b || c || d){ A = c; cout << dfs(a,b,d,1,1) << endl; } }