问题传送门：

题意：

给你一个分数，p/q ， a ， n
要求 1/x1 + 1/x2 + 1/x3 +......+ 1/xk = p/q
                                    k <= n
且 x1 * x2 * x3 * ..... * xk <= a

即把 p / q ，分解成子分数的和，
子分数的分子为 1 ，分母最大是 n ，分母累乘 <= a .
问最多有多少种分解方案。

分析：

a 最大是 12000， 并且 n 最大是7 
这一题可以用 DFS 暴力搜索出所有的分解情况。
下面代码的DFS中，cnt记录的是已经分解了几个子分数，初始是0，
prq 记录的是上一个子分数的分子，那么这一次的搜索也是从prq开始
sump，sumq记录的是目前自分子的和
如果目前子分数的和满足答案，ans++，不return，而是继续向下搜索
如果目前子分数的和超过了，跳过，继续向下搜索
如果目前子分数的和小于要求，深搜下一个子分数，cnt+1

代码：

#include <iostream>

using namespace std;

int ans, p, q, a, n;

void DFS(int cnt, int prq, int sump, int sumq, int mul)
{  
    if (cnt > n) return ;
    // 暴力枚举拆分的分数的分母
    int np, nq;
    for(int i = prq; i*mul <= a; i++)
    {
        np = sumq + i*sump;
        nq = i*sumq;
        // 如果分解的分数的和，加上当前枚举的分数已经过大了，跳过，继续下次枚举
        if (np*q > nq*p)
            continue;
        if (np*q==nq*p)
        {
            ans++;
            continue;
        }
        DFS(cnt+1, i, np, nq, mul*i);
    }
}

int main()
{
    while (cin >> p >> q >> a >> n && (p+q+a+n))
    {
        ans = 0;
        DFS(1, 1, 0, 1, 1);
        cout << ans << endl;
    }
    return 0;
}