ICPC 国内予選2004C Unit Fraction Partition AOJ 1131

解法
深さ優先探索で、（int 分子、int 分母、int 分母の積、int 今何個目の数か、int 現在の分母の値）を管理しながらやる。

ここで、n = 3の時、
とすればよい。

#include <bits/stdc++.h>
#include <map>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
//typedef pair<double, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
//const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};


const double INF = 1000000.0;
const int MAX_V = 35;
struct edge{ int to,cost,rest;};
//typedef pair<int,int> P;
typedef pair<int, int> P;
typedef pair<double,T> PP;


int p,q,a,n;
int ans;

int check(int ss,int bb){
    if(p * bb == q * ss){
        return 0;
    }else if(p*bb > q*ss){
        return 1;
    }else{
        return -1;
    }
}

void dfs(int s,int b,int asum,int num,int x){
    int tmp = check(s,b);
    if(tmp == 0){ //same
        ans++;
        return;
    }else if(tmp == 1 && num != n){//continue
        for(int i = x;i <= a;i++){
            if(i * asum > a)break;
            dfs(s*i+b,b*i,asum*i,num+1,i);
        }
    }
    return;
}

int main(){
    while(true){
        cin >> p >> q >> a >> n;
        if(p + q + a + n == 0)break;
        ans = 0;
        for(int i = 1;i <= a;i++){
            dfs(1,i,i,1,i);
        }
        cout << ans << endl;
    }
}