Unit Fraction Partition
Time Limit:1000MS |
|
Memory Limit:30000K |
Total Submissions:3824 |
|
Accepted:1500 |
Description
A fraction whose numerator is 1 and whose denominator is a positive integer is called a unit fraction. A representation of a positive rational number p/q as the sum of finitely many unit fractions is called a partition of p/q into unit fractions. For example,
1/2 + 1/6 is a partition of 2/3 into unit fractions. The difference in the order of addition is disregarded. For example, we do not distinguish 1/6 + 1/2 from 1/2 + 1/6.
For given four positive integers p, q, a, and n, count the number of partitions of p/q into unit fractions satisfying the following two conditions.
The partition is the sum of at most n many unit fractions.
The product of the denominators of the unit fractions in the partition is less than or equal to a.
For example, if (p,q,a,n) = (2,3,120,3), you should report 4 since
enumerates all of the valid partitions.
Input
The input is a sequence of at most 200 data sets followed by a terminator.
A data set is a line containing four positive integers p, q, a, and n satisfying p,q <= 800, a <= 12000 and n <= 7. The integers are separated by a space.
The terminator is composed of just one line which contains four zeros separated by a space. It is not a part of the input data but a mark for the end of the input.
Output
The output should be composed of lines each of which contains a single integer. No other characters should appear in the output.
The output integer corresponding to a data set p, q, a, n should be the number of all partitions of p/q into at most n many unit fractions such that the product of the denominators of the unit fractions is less than or equal to a.
Sample Input
2 3 120 3
2 3 300 3
2 3 299 3
2 3 12 3
2 3 12000 7
54 795 12000 7
2 3 300 1
2 1 200 5
2 4 54 2
0 0 0 0
Sample Output
4
7
6
2
42
1
0
9
3
Source
#include<iostream>
#include<cmath>
using namespace std;
double E=0.0000000001;
int counter=0,N,A;
int dfs2(double sum,int num,int product,int t){
if(t>N||product>A||(sum<0&&abs(sum)>=E))
return 0;
if(abs(sum)<E){
counter++;
return 1;
}
for(int i=num;;i++){
if(1.0/i*(N-t)<sum)
break;
else{
dfs2(sum-1.0/i,i,i*product,t+1);
}
}
return 1;
}
int main(){
int p,q,a,n;
while(true){
cin>>p>>q>>A>>N;
dfs2(p*1.0/q,2,1,0);
cout<<counter<<endl;
}
}
分享到:
相关推荐
Fraction代码参考Fraction代码参考Fraction代码参考
定义一个分数类(Fraction) 实例变量:分子,分母 方法:初始化方法(2个参数),便利构造器,约分,打印,加,减,乘,除。
fraction的pde版代码
简单的C++分数类实现,包含运算符的实现和重载
用c++写了个class fraction
1.自定义分数类fraction,使用该类可以完成分数的输入、分数的加、减、乘、除二目运算和一目减运算、分数的约分操作、分数的倒数运算、对两个分数进行六种比较运算、以及对分数的输出等操作。 2.将其中使用的普通...
Fraction.java
参考_fraction.cpp
this is a traditional book about continued fraction.
Fraction类使用属性的方法,实现了分数的约分,打印,加法,减法,乘法,除法四则运算
Fraction.js, 在JavaScript中,分数是一个有理数字 对inprecise数表示的数值疲劳,必须存储有理和无理数,如PI或者 sqrt(2) 。 显然,以下问题是可以预防的:1 / 98 * 98 // = 0.9999999999999999如果需要更精确,...
分式的计算 赋值 定义 拷贝 重载各种操作符 支持各种运算 gcd 简化
设计一个表示分数的类Fraction。这个类用两个int类型的变量分别表示分子和分母。具体细节请参考压缩包中的readme.txt文件!
ClassFraction20211122.cpp
Fraction_Calculator.zip
Fraction.js-JavaScript中的ℚ 厌倦了用双精度数表示的不精确数字,这些数字必须以相同的方式存储有理数和无理数,例如PI或sqrt(2)? 显然,以下问题是可以避免的: 1 / 98 * 98 // = 0.9999999999999999 如果...
Fraction_Calculator_V2.cpp
分数它是通过BigInteger实现的。 .Net Framework的最低...即将推出的功能减少分数从浮点数/双精度数/小数转换为小数例子Fraction f1 = " 0.5 " ;// 1/2Fraction f2 = " 1.2/0.6 " ;// 2/1Fraction f3 = f1 + f2 ;// 5/2
例如,本类中,对于添加方法,将会有添加和添加自校正,顾名思义,其中的计算仅在本对象内完成,过程中完全不会出现任何对象创建,xxxSelf的方法全为对因此,在程序的需求允许使用自我方法时,尽量使用自我方法,...