int?s,//?分母的最小值
long?long?fz,//?剩余未分配部分大小的分子
long?long?fm)//?剩余未分配部分大小的分母
{
//?如果需要查找最後壹個分式
if?(cur?==?n)
{
//?如果分母不能被分子整除，則最後壹個分式無法構成
if?(fm?%?fz)
return;//?從搜索中退回
//?最後壹個分式的分母
a[cur]?=?fm?/?fz;
//?如果最後壹個分式的分母大於30，從搜索中返回
if?(a[n]?>?30)
return;//?從搜索中退回
//?把所有的分式打印出來
for?(int?i?=?0;?i?<?n;?i++)
printf("1/%d?",?(int)a[i]);
printf("1/%d\n",?(int)a[n]);
return;//?從搜索中退回
}
//?計算下壹個分母的最小值
s?=?(int)max(s?*?1LL,?fm?/?fz?+?1);
int?i;
long?long?A,?B,?Gcd;
//?枚舉所有可能的下壹個分母
for?(i?=?s;;?i++)
{
//?假設後面所有的分式全部的分母都是?i，也不能夠使得總和達到?fz?/?fm
if?(i?*?fz?>=?fm?*?(n?-?cur?+?1))
break;//?不再枚舉更大的分母
//?設定當前分式的分母為?i
a[cur]?=?i;
//?剩余分數的分母
B?=?fm*i;
//?剩余分數的分子
A?=?fz*i?-?fm;
//?求最大公約數
Gcd?=?gcd(A,?B);
//?深搜，求下壹個分式，而且最小分母是?i?+?1，剩余分數的分子分母都約分
dfs(cur?+?1,?i?+?1,?A?/?Gcd,?B?/?Gcd);
}
return;
}