AOJ 1131 Unit Fraction Partition

問題文: 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;
	}		
}