题意分析

我们需要解决的问题是：将一个正有理数
$\frac{p}{q}$分解为最多 n 个单位分数（即形如 $\frac{1}{k}$的分数）之和，且这些单位分数的分母乘积不超过 a。统计满足条件的分解方式的数量。

关键点： 单位分数分解：将 $\frac{p}{q}$表示为$\frac{1}{k_i}+\frac{1}{k_2}+···+\frac{1}{k_m}$,其中 m≤n，且 $k_1×k_2×···×k_m≤a$

顺序无关性：分解中单位分数的顺序不影响结果

输入输出约束： 输入最多包含 200 组数据，每组数据为 $(p,q,a,n)$，满足 $p,q≤800、a≤12000、n≤7$。 输出为每组数据对应的分解方式数量。

解题思路

1.方法选择 由于 n≤7 且 a≤12000，直接暴力搜索所有可能的分解方式是可行的。具体步骤如下：

2.深度优先搜索（DFS）： 从当前剩余的分数$\frac{p}{q}$出发，尝试用单位分数 $\frac{1}{k}$ 逐步消减分子，直到满足以下条件之一：

剩余分数为 0（即找到一种分解方式）。

剩余分数无法被进一步分解（剪枝）。

在搜索过程中，维护以下状态： 当前剩余分数的分子 p 和分母 q。

当前分母的乘积 mod（初始为 1）。

当前尝试的单位分数分母的最小值 x（避免重复计数）。

剩余可用的单位分数数量 t。

3.剪枝优化： 如果剩余分数的分子 $p×x>q×t$（即当前单位分数无法在剩余步数内消减分子），则剪枝。 如果分母乘积$mod×x>a$，则剪枝。

代码实现

#include<cstdio>
#include<cstring>
int a,n,ans;
void dfs(int p,int q,int mod,int x,int t)  
{
	if(p==0&&mod<=a)  
	{
		ans++;
		return;
	}
	if(t==0||p*x>q*t||mod*x>a)  
		return;
	for(int i=x;i<=a;i++)   
	{
		if(mod*i<=a) 
		{
			int xt=p*i-q;   
			if(xt>=0)       
				dfs(xt,q*i,mod*i,i,t-1);
		}
		else         
			break;
	}
}
int main()
{
	int p,q;
	while(~scanf("%d%d%d%d",&p,&q,&a,&n)&&(p||q||a||n))
	{
		ans=0;
		dfs(p,q,1,1,n);
		printf("%d\n",ans);
	}
}