単位分数分割（競技プログラミング２０１３　３．２）

code.cc

#include <iostream>
using namespace std;

int solve(int p, int q, int a, int i, int n, int last, int cp, int cq){
	/*
	変数それぞれ
		指定の分子（固定）
		指定の分母（固定）
		cq*cpの上限（固定）
		深さの上限(固定)
		これ以降を調べる
		足しこんでる分子
		足しこんでる分母
	*/
	
	/*
	この関数内でやること
	１．この４つをループ（次の兄弟枝へ遷移）
		１．１．(1/d)を足しこむ
		１．２．結果が(p/q)を超えたら探索打ち切りで次の枝へ
		１．３．結果が(p/q)になったら結果を+1し探索打ち切りで次の枝へ
		１．４．足しこんだ結果を用いて深い枝へ探索（再帰）
	２．結果を返す
	*/
	
	if(n < i)
		return 0;
		
	int sum = 0;
	
	for(int d = last; d <= a && cq * d <= a; ++d){
		// cp/cq + 1/d = (cp * d + cq) / (cq * d)
		int cp2 = cp * d + cq;
		int cq2 = cq * d;
		
		// cp2/cq2 > p/q
		if(cp2 * q > cq2 * p)
			continue;
			
		if(cp2 * q == cq2 * p){
			sum++;
			continue;
		}
		
		sum += solve(p, q, a, i + 1, n, d, cp2, cq2);
		
	}
	
	return sum;
}

int main(void){
	
	for(int p, q, a, n; cin >> p >> q >> a >> n,(p || q || a || n);){
		
		cout << solve(p, q, a, 1, n , 1, 0, 1) << endl;
		
	}
	
	return 0;
	
}

input.txt

2 3 120 3
2 3 300 3
2 3 299 3
2 3 12 3
2 3 12000 7
54 795 12000 7
2 3 300 1
2 1 200 5
2 4 54 2
0 0 0 0

run.bat

cmd /k "g++ code.cc & a.exe < input.txt"