蓝桥杯2020年第十一届国赛真题-循环小数

题目

题目链接

题解

数论。

存在这么一个结论。

纯循环小数转化为分数：如0.4285742857…

找到循环体42857，该循环体有5位，故而0.4285742857…就是42857/99999，这里有5个9

满足公式 x y = 循 环 体 1 0 循 环 体 位 数 − 1 \frac{x}{y}=\frac{循环体}{10^{循环体位数}-1} yx​=10循环体位数−1循环体​

混合循环小数转化为分数：如0.14285742857…

先转换为0.1 + (0.4285742857…)/10，对于(0.4285742857…)部分我们重复上面的过程即可，即 1/10 + 42857/99999/10。

为了方便实现，我们直接将两部分通分，得到 99999/999990 + 42857/999990 = （99999 + 42857)/999990 = (1000000 - 1 + 42857)/999990 = (142857 - 1)/999990

可以看出分子其实就是整个小数部分（不严谨，你懂就行）减去非循环部分的值；分母是10的“整个小数部分的位数”次方减去10的“循环体部分的位数-1”次方。

二者求最大公约数，分子分母同除最大公约数，得到最简分数。

代码

#include
using namespace std;
typedef long long LL;
int main()
{
	int p, q;
	LL decimal;
	cin >> p >> q;
	cin >> decimal;
	
	LL x = decimal - decimal / (LL) pow (10, q-p+1);
	LL y = (LL) pow (10, q) - (LL) pow (10, p-1);
	
	LL gcd = __gcd (x, y);
	
	cout