It is easy to see that for every fraction in the form(k> 0), we can always find two positive integersxandy,x≥y, such that:
.
Now our question is: can you write a program that counts how many such pairs ofxandythere are for any givenk?
Input
Input contains no more than 100 lines, each giving a value ofk(0 <k≤ 10000).
Output
For eachk, output the number of corresponding (x,y) pairs, followed by a sorted list of the values ofxandy, as shown in the sample output.
Sample Input
2 12
Sample Output
2 1/2 = 1/6 + 1/3 1/2 = 1/4 + 1/4 8 1/12 = 1/156 + 1/13 1/12 = 1/84 + 1/14 1/12 = 1/60 + 1/15 1/12 = 1/48 + 1/16 1/12 = 1/36 + 1/18 1/12 = 1/30 + 1/20 1/12 = 1/28 + 1/21 1/12 = 1/24 + 1/24
更好的测试数据:
In:
3 1 4 15 92 653 589 793 2384 626 4338 3279 502 88
Out:
2 1/3 = 1/12 + 1/4 1/3 = 1/6 + 1/6 1 1/1 = 1/2 + 1/2 3 1/4 = 1/20 + 1/5 1/4 = 1/12 + 1/6 1/4 = 1/8 + 1/8 5 1/15 = 1/240 + 1/16 1/15 = 1/90 + 1/18 1/15 = 1/60 + 1/20 1/15 = 1/40 + 1/24 1/15 = 1/30 + 1/30 8 1/92 = 1/8556 + 1/93 1/92 = 1/4324 + 1/94 1/92 = 1/2208 + 1/96 1/92 = 1/1150 + 1/100 1/92 = 1/621 + 1/108 1/92 = 1/460 + 1/115 1/92 = 1/276 + 1/138 1/92 = 1/184 + 1/184 2 1/653 = 1/427062 + 1/654 1/653 = 1/1306 + 1/1306 5 1/589 = 1/347510 + 1/590 1/589 = 1/18848 + 1/608 1/589 = 1/11780 + 1/620 1/589 = 1/1550 + 1/950 1/589 = 1/1178 + 1/1178 5 1/793 = 1/629642 + 1/794 1/793 = 1/49166 + 1/806 1/793 = 1/11102 + 1/854 1/793 = 1/4514 + 1/962 1/793 = 1/1586 + 1/1586 14 1/2384 = 1/5685840 + 1/2385 1/2384 = 1/2844112 + 1/2386 1/2384 = 1/1423248 + 1/2388 1/2384 = 1/712816 + 1/2392 1/2384 = 1/357600 + 1/2400 1/2384 = 1/179992 + 1/2416 1/2384 = 1/91188 + 1/2448 1/2384 = 1/46786 + 1/2512 1/2384 = 1/40528 + 1/2533 1/2384 = 1/24585 + 1/2640 1/2384 = 1/21456 + 1/2682 1/2384 = 1/11920 + 1/2980 1/2384 = 1/7152 + 1/3576 1/2384 = 1/4768 + 1/4768 5 1/626 = 1/392502 + 1/627 1/626 = 1/196564 + 1/628 1/626 = 1/98595 + 1/630 1/626 = 1/1878 + 1/939 1/626 = 1/1252 + 1/1252 23 1/4338 = 1/18822582 + 1/4339 1/4338 = 1/9413460 + 1/4340 1/4338 = 1/6277086 + 1/4341 1/4338 = 1/4708899 + 1/4342 1/4338 = 1/3140712 + 1/4344 1/4338 = 1/2095254 + 1/4347 1/4338 = 1/1572525 + 1/4350 1/4338 = 1/1049796 + 1/4356 1/4338 = 1/701310 + 1/4365 1/4338 = 1/527067 + 1/4374 1/4338 = 1/352824 + 1/4392 1/4338 = 1/236662 + 1/4419 1/4338 = 1/178581 + 1/4446 1/4338 = 1/120500 + 1/4500 1/4338 = 1/82422 + 1/4579 1/4338 = 1/62419 + 1/4662 1/4338 = 1/43380 + 1/4820 1/4338 = 1/30366 + 1/5061 1/4338 = 1/23859 + 1/5302 1/4338 = 1/17352 + 1/5784 1/4338 = 1/13014 + 1/6507 1/4338 = 1/10845 + 1/7230 1/4338 = 1/8676 + 1/8676 5 1/3279 = 1/10755120 + 1/3280 1/3279 = 1/3587226 + 1/3282 1/3279 = 1/1197928 + 1/3288 1/3279 = 1/13116 + 1/4372 1/3279 = 1/6558 + 1/6558 5 1/502 = 1/252506 + 1/503 1/502 = 1/126504 + 1/504 1/502 = 1/63503 + 1/506 1/502 = 1/1506 + 1/753 1/502 = 1/1004 + 1/1004 11 1/88 = 1/7832 + 1/89 1/88 = 1/3960 + 1/90 1/88 = 1/2024 + 1/92 1/88 = 1/1056 + 1/96 1/88 = 1/792 + 1/99 1/88 = 1/572 + 1/104 1/88 = 1/440 + 1/110 1/88 = 1/330 + 1/120 1/88 = 1/264 + 1/132 1/88 = 1/209 + 1/152 1/88 = 1/176 + 1/176
In:
2 12 8999 10000
Out:
2 1/2 = 1/6 + 1/3 1/2 = 1/4 + 1/4 8 1/12 = 1/156 + 1/13 1/12 = 1/84 + 1/14 1/12 = 1/60 + 1/15 1/12 = 1/48 + 1/16 1/12 = 1/36 + 1/18 1/12 = 1/30 + 1/20 1/12 = 1/28 + 1/21 1/12 = 1/24 + 1/24 2 1/8999 = 1/80991000 + 1/9000 1/8999 = 1/17998 + 1/17998 41 1/10000 = 1/100010000 + 1/10001 1/10000 = 1/50010000 + 1/10002 1/10000 = 1/25010000 + 1/10004 1/10000 = 1/20010000 + 1/10005 1/10000 = 1/12510000 + 1/10008 1/10000 = 1/10010000 + 1/10010 1/10000 = 1/6260000 + 1/10016 1/10000 = 1/5010000 + 1/10020 1/10000 = 1/4010000 + 1/10025 1/10000 = 1/3135000 + 1/10032 1/10000 = 1/2510000 + 1/10040 1/10000 = 1/2010000 + 1/10050 1/10000 = 1/1572500 + 1/10064 1/10000 = 1/1260000 + 1/10080 1/10000 = 1/1010000 + 1/10100 1/10000 = 1/810000 + 1/10125 1/10000 = 1/791250 + 1/10128 1/10000 = 1/635000 + 1/10160 1/10000 = 1/510000 + 1/10200 1/10000 = 1/410000 + 1/10250 1/10000 = 1/400625 + 1/10256 1/10000 = 1/322500 + 1/10320 1/10000 = 1/260000 + 1/10400 1/10000 = 1/210000 + 1/10500 1/10000 = 1/170000 + 1/10625 1/10000 = 1/166250 + 1/10640 1/10000 = 1/135000 + 1/10800 1/10000 = 1/110000 + 1/11000 1/10000 = 1/90000 + 1/11250 1/10000 = 1/88125 + 1/11280 1/10000 = 1/72500 + 1/11600 1/10000 = 1/60000 + 1/12000 1/10000 = 1/50000 + 1/12500 1/10000 = 1/42000 + 1/13125 1/10000 = 1/41250 + 1/13200 1/10000 = 1/35000 + 1/14000 1/10000 = 1/30000 + 1/15000 1/10000 = 1/26000 + 1/16250 1/10000 = 1/25625 + 1/16400 1/10000 = 1/22500 + 1/18000 1/10000 = 1/20000 + 1/20000
初次尝试的AC解法,要测试精度!应该有更好的解法,能绕过精度问题
#define RUN #ifdef RUN #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #include <string> #include <iostream> #include <sstream> #include <map> #include <set> #include <vector> #include <list> #include <cctype> #include <algorithm> #include <utility> #include <math.h> using namespace std; #define LL long long #define MAXN 10001 LL xbuf[MAXN]; LL ybuf[MAXN]; void printout(LL k, LL n){ printf("%lld\n", n); for(int i=0; i<n; i++){ printf("1/%lld = 1/%lld + 1/%lld\n", k, xbuf[i], ybuf[i]); } } void play(LL k){ LL y = 1; LL cnt = 0; memset(xbuf, 0, sizeof(xbuf)); memset(ybuf, 0, sizeof(ybuf)); for(y=1; y<=2*k; y++){ double x = 1.0 / (1.0/k - 1.0/y); LL xInt = (LL)(x+0.5); // 经过确定精度,选用1e-4,过大或过小都不能AC if(x>0 && fabs(x-xInt)<1e-4){ //printf("x:%lf, xInt:%lld, y:%lld\n", x, xInt, y); xbuf[cnt] = xInt; ybuf[cnt] = y; cnt++; } } printout(k, cnt); } int main(){ #ifndef ONLINE_JUDGE freopen("10976.in", "r", stdin); freopen("10976.out", "w", stdout); #endif LL k; while(scanf("%lld",&k) != EOF){ play(k); } } #endif
相关推荐
Manhattan GMAT Math-Fractions, Decimals & Percents.pdf
python-fractions-process:第二个进入我的创客交易会网站的页面,我在其中日记并解释编写python fractions脚本的过程
分数型 来自 JB (Joe) Rainsberger 的在线课程 [ 世界上最好的 TDD 介绍”)
" https://www.random.org/decimal-fractions/?num=1&dec=9&col=1&format=plain " ; Async .start(seq() { // concurrently request for 10 random numbers var numberTasks = Seq .range( 0 , 10 ) | > Seq ....
尼姆分数 Nim Fractions 库是一个用于有理数算术的简单库。 执照 Nim Fractions 根据 MIT 许可条款提供。 有关详细信息,请参阅许可证文件。 安装 $ nimble install fractions
部分分形 Java库,用于简化分数函数
连续分数 Haskell库,用于处理和评估连续分数。
Neverending Fractions: An Introduction to Continued Fractions
使用在极坐标图上显示[0,1]范围内的每个分数。 受启发。
资源来自pypi官网。 资源全名:binary_fractions-1.0.2.tar.gz
As continued fractions become more important again, in part due to their use in finding algorithms in approximation theory, this timely book revives the approach of Wallis, Brouncker and Euler and ...
Ruby级分 杰克·理查兹(Jack Richards)撰写 一个简单的程序,通过为每个枚举的有理数分配一个唯一的自然数作为标签来证明有理数是可数的。 理论/资料来源 程序的基本功能依赖于一系列函数,在所有自然数N到所有...
资源分类:Python库 所属语言:Python 资源全名:django_fractions-0.3.1-py2.py3-none-any.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
这本数学书里面有很多连分数公式 是一本好书This book is aimed at two kinds of readers: firstly, people working in or near mathematics, who are curious about continued fractions; and secondly, senior or ...
Special functions are pervasive in all ... We emphasise that only 10% of the continued fractions contained in this book, can also be found in the Abramowitz and Stegun project or at the Wolfram website!
As continued fractions become more important again, in part due to their use in finding algorithms in approximation theory, this timely book revives the approach of Wallis, Brouncker and Euler and ...
作者: Oleg Karpenkov 出版社: Springer ISBN: 9783642393679
This book is aimed at two kinds of readers: firstly, people working in or near mathematics, who are curious about continued fractions; and secondly, senior or graduate students who would like an ...
Write a program that will accept a fraction of the form N/D, where N is the numerator and D is the denominator and print the decimal representation. If the decimal representation has a repeating ...