/*
* 本以為這題剪枝會很難，沒想到1A了。。32ms
* 這個題的難點是分數的處理。。不要用double。。精度難以把握。。
*
*/

#include <cstdio>
#include <cmath>
using namespace std;

int p, q, a, n, tot; //如題目定義，tot為答案

//p1/q1 和 p2/q2 比較大小
int inline frac_cmp(int p1, int q1, int p2, int q2){
return p1 * q2 - p2 * q1;
}
/*
int inline gcd(int a, int b){
if(b == 0) return a;
return gcd(b, a % b);
}
*/
// p/q - 1/d 答案保存在 p/q中
void inline frac_sub(int &p, int &q, int d){
p = p * d - q;
q = q * d;

//可以不約分，節省時間（600ms -> 63ms）
// if(p != 0){
// int g = gcd(p, q);
// p = p / g; q = q / g;
// }
}

//last_d上一層的分母。。left_p剩下的分數的分子。。left_q剩下的分數的分母。。num層數。。left_a剩下的分母的最大乘積
void dfs(int last_d, int left_p, int left_q, int num, int left_a){
int next_p, next_q;
if(num == n+1 && left_p != 0) return;
if(num <= n+1 && left_p == 0){
tot++; return;
}

// if(frac_cmp(left_p, left_q, n-num+1, last_d) > 0) return; //剩下的分數太大(后面會判斷，可略)

for(int d=last_d; d<=left_a; d++){
if(frac_cmp(left_p, left_q, 1, d) < 0) continue; // 1/d太大

frac_sub(next_p = left_p, next_q = left_q, d); //求得next_p, next_q
if(frac_cmp(next_p, next_q, n-num, d) > 0) break; //剩給下一層的分數太大

dfs(d, next_p, next_q, num+1, left_a / d);
}

}


int main(){
while(scanf("%d %d %d %d", &p, &q, &a, &n)){
if(p==0) return 0;

tot = 0;
dfs(1, p, q, 1, a);
printf("%d\n", tot);

}

return 0;

}

總結

以上是生活随笔為你收集整理的poj-1980 Unit Fraction Partition **的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。