1131: Unit Fraction Partition

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1131&lang=jp

解き直し。
y/x+1/z=(yz+x)/xz
だから、これを使って探索。枝刈りはしなくても通る。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int p,q,a,n;

int rec(int x,int y,int now,int dep){
  
  if(x*p==q*y)return 1;
  if(dep==0)return 0;

  int sum=0;
  for(int z=now;z*x<=a;z++){
    if(y/x+1/z<=p/q)sum+=rec(z*x,z*y+x,z,dep-1);
  }
  return sum;
}

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

  return 0;
}