【题解】分数化小数(无限循环小数计数 欧拉函数 循环节 十进制 欧拉定理)

分数化小数

题目描述

对于一个分数(不一定是最简形式),给出它的小树形式,如果小数有循环节的话,把循环节放在一对圆括号中.
例如,1/4 =0.25,1/3=0.3333写成0.(3)1/7=0.142857142857...写成0.(142857)。如果结果是一种整数xxx,则用xxx.0 等表示整数xxx
输入包括一行,包括被空格分隔开的分子N和分母D(第一个是N,第二个是D)。
输出包括一行,为转换后的小数形式。

输入样例

45 56

输出样例

0.803(571428)

题目解释

题目中需要求一个 分数 的小数,如果是无限循环小数,则输出 0.xxx(xxx) 的格式。
因此我们考虑,先求出这个小数的 循环起始点(S)循环长度(T)

我们举个栗子。对于 $ x = \frac{45}{56} $ 这种情况。
我们考虑先对 $x * 10$ 即: $\frac{45}{46},\frac{450}{46},\frac{4500}{46},\frac{45000}{46}\cdots$
然后我们将这些分数进行 模 46 操作, 即:

我们可以明显的发现当操作进行到第 10 次的时候和第 4 次重复了,显然已经形成了一个长度为 6 的循环节,即从第 4 项开始循环。

由此我们可以推广到更一般的情况,假设存在 $\frac{p}{q}$由于小数部分和整数无关,因此我们可以假设这个分数为真分数。不妨假设$p>q$。

由上可知,我们可以把第 $k$ 个分数写成
因此我们可以假设第 $i$ 个分数和第 $j$ 个分数相等,即构成了一个循环节。有
又可表示为

令 $g = gcd(p,q)$,设 $p = p’g$ , $q=q’g$ 。即

由此可知
因为 $p’$ 和 $q’$ 互质,因此可得$q’|10^i(10^{j - i} - 1)$。
由于 $10^i$ 为偶数,且 $(10^{j - i} - 1)$ 为奇数。
显然 $i$ 由 $10^i$ 和 $q’$ 共同决定。又知 $10^i$ 和 $q’$ 由 $2$ 和 $5$ 贡献。
因此 $i = max(n,m)$,$n$ 为 $q’$中贡献的 $5$ 的个数, $m$ 为 $q’$中贡献的 $10$ 的个数。

接下来需要求循环节 $T = j - i$。


经过一番计算,上式 $q’|10^i(10^{j - i} - 1)$ 已经变成了

又知 $q’’$ 与 $\frac{10^i}{5^n10^m}$ 互质。式子可化简为
只需要解出 $j -i$ 就是我们无限循环小数中的循环节了。即

不妨假设 $x = j - i$,即解
由欧拉定理可知,存在最小的 $10^x≡1\ (mod\ q’’)$ ,当 $x$ 是 $\varphi(q’’)$ 的一个因子。
因此我们只需要去枚举所有 $\varphi(q’’)$ 的因子,从而找到一个最小的 $x$,使得 $10^x≡1\ (mod\ q’’)$。

此时解出的 $i$ 就是循环节开始的前一位,$x$ 即 $j - i$ 为循环节的长度。
接下来的任务只需要模拟乘法,按照题目要求输出即可。

但是非常悲伤的事情是,队友暴力模拟 A 了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL p, q, S, T, Z;

LL Euler(LL x) {
LL ans = x;
for (LL i = 2; i * i <= x; i++) {
if (x % i == 0) {
ans = (ans/i) * (i - 1);
while (x % i == 0) x /= i;
}
}
if (x > 1) ans = (ans/x) * (x - 1);
return ans;
}

LL power(LL a, LL x, LL mod) {
LL ans = 1;
while (x) {
if (x & 1) ans = (ans * a)%mod;
a = (a * a)%mod;
x >>= 1;
}
return ans;
}

LL gcd(LL a, LL b) {
return b == 0? a:gcd(b, a%b);
}

LL get_first(LL &x) {
LL ans1 = 0, ans2 = 0;
while (x % 2 == 0) {
x /= 2;
ans1++;
}
while (x % 5 == 0) {
x /= 5;
ans2++;
}
return max(ans1, ans2);
}

LL get_T(LL x, LL mod) {
LL Min = 1e18;
for (LL i = 1; i * i <= x; i++) {
if (x % i == 0) {
if (power(10, i, mod) == 1) {Min = min(Min, i); break;}
if (power(10, x/i, mod) == 1) Min = min(Min, x/i);
}
}
return Min;
}

void print(LL p, LL q, LL S, LL T) {
printf("%lld.", p/q);
p -= q * (p/q);
for (int i = 0; i < S + T; i++) {
if (i == S) printf("(");
p *= 10;
printf("%lld", p/q);
p -= q * (p/q);
if (p == 0) break;
if (i == S + T - 1) printf(")");
}
printf("\n");
}

int main()
{
while (scanf("%lld %lld", &p, &q) != EOF) {
LL a = p, b = q;
LL g = gcd(p, q);
p /= g, q /= g;

S = get_first(q);
LL phi = Euler(q);
T = get_T(phi, q);

if (T == 1e18) S = T;
print(a, b, S, T);
}

return 0;
}