らての精進日記

修行をします

aoj1131:Unit Fraction Partition

解法

再帰を使って数え上げた。愚直にやるとTLEするが、自明な枝刈りを入れると通る。

今見ている分子と分母をそれぞれ{\displaystyle p',q'}とすると、{\displaystyle \frac{p'}{q'} > \frac{p}{q}}なら探索を打ち切る。実数は怖いので分母を払って{\displaystyle p'q>pq'}とするとよい。

コード

#include<bits/stdc++.h>
using namespace std;
#define int long long
int P,Q,A,N;

int dfs(int p,int q,int n,int t){
    if(P*q==p*Q)return 1;
    if(P*q<p*Q)return 0;
    if(N==n)return 0;

    int ret=0;

    for(int i=t;q*i<=A;i++){
        ret+=dfs(p*i+q,q*i,n+1,i);
    }

    return ret;
}

signed main(){
    while(cin>>P>>Q>>A>>N,P||Q||A||N)
        cout<<dfs(0,1,0,1)<<endl;
    return 0;
}