单位分数分割(fraction)

单位分数分割(fraction)

测试数据来自 wjszez/1593

分子是1而分母是正整数的分数叫做单位分数。把一个正有理数p/q分成有限多个单位分数的和的表达形式叫做p/q的单位分数分割。例如,1/2+1/6就是2/3的一种单位分数分割。如果只是相加顺序不同,则被看成同一种分割。例如,1/6+1/2与1/2+1/6是一样的。
对于给出的四个正整数p,q,a,n,要求给出满足以下两个条件的p/q的单位分数分割的不同方式的总数。
1、单位分数最多有n个。
2、所有单位分数分母的乘积小于等于a。
例如,当(p,q,a,n)=(2,3,120,3)时,你应该输出4,因为

这样列出所有正确的分割。

输入 fraction.in
输入包括四个正整数p,q,a,n。满足p,q<=800,a<=12000,n<=7。数据间由一个空格隔开。

输出 fraction.out
输出一行只有一个整数。不应该有其他字符存在。

样例输入
2 3 12000 7

样例输出
42

信息

ID
2005
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者