试题 G: 循环小数
时间限制: 1.0s 内存限制: 256.0MB 本题总分：20 分
【问题描述】
已知 S 是一个小于 1 的循环小数，请计算与 S 相等的最简真分数是多少。
例如 0 . 3333 · · · 等于 1/3
，0 . 1666 · · · 等于 1/6。
【输入格式】
输入第一行包含两个整数 p 和 q，表示 S 的循环节是小数点后第 p 位到第q 位。
第二行包含一个 q 位数，代表 S 的小数部分前 q 位。
【输出格式】
输出两个整数，用一个空格分隔，分别表示答案的分子和分母。
【样例输入】
1 6
142857
【样例输出】
1 7
【评测用例规模与约定】
对于所有评测用例，1 ≤ p ≤ q ≤ 10。
解题思路
该题就是运用循环小数的特点：
-
纯循环小数转化为分数：如0.4285742857…
找到循环体42857，该循环体有5位，故而0.4285742857…就是42857/99999，这里有5个9
这个公式自已也可以推导，对于真分数X/Y来说，
X/Y = L/(10^n - 1)
其中L为循环节，n为循环节位数
-
混合循环小数转化为分数：如0.14285742857…
大致方法和1中类似，不过注意的是这里的0.1不在循环体内，但可以转化为
0.1+(0.4285742857...)/10，0.1转换为分数1/10，循环体部分用1中的方法来得到分数再/10即可。1/10+42857/99999/10。如果要得到最简分数，那么可以使用辗转相除法求得二者的最大公约数，之后再用最大公约数同时除以分子和分母即可。
程序(c++)
#include <bits/stdc++.h>using namespace std;
long gcdMax(long x, long y);int main()
{long a, b;long L, _L; //L存放循环体long F = 0; //F存放非循环体部分long X = 0, Y = 0; //X为分子，Y为分母，最终输出结果long gcd = 1; //最大公约数cin >> a >> b;cin >> _L;F = _L/pow(10, b-a+1);X = _L - F;Y = pow(10, b) - pow(10, a-1);gcd = gcdMax(X, Y);X /= gcd;Y /= gcd;cout << X << " " << Y << endl;return 0;
}/*辗转相除法求最大公约数*/
long gcdMax(long x, long y)
{long temp = 1;if(x > y) {temp = x;x = y;y = temp;}//x位较小值，y位较大值while((y%x) != 0){temp = y%x;y = x;x = temp;}return(x);
}
结果
yocin@ubuntu:~/Documents/cppPractice$ ./main
1 6
142857
1 7 # 输出，表示1/7
