题意:
给你一个分数,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;
}
Comments | NOTHING