题解 | #小红的循环节长度#

参考：如何找到一个循环小数循环节？

欧拉定理

维基百科｜欧拉定理

简单说就是，如果$aa$和$bb$为正整数，且互为质数也就是$gcd(a,b)=1gcd(a,\; b)\; =\; 1$，那么：

该式表示$a^{\mathrm{\Phi }(b)}a^\{\backslash Phi(b)\}$与1在模$bb$下同余，即$a^{\mathrm{\Phi }(b)}\mathrm{\%}b=1a^\{\backslash Phi(b)\}\; \backslash ;\; \backslash \%\; \backslash ;\; b\; =\; 1$，其中$\mathrm{\Phi }(b)\backslash Phi(b)$为欧拉函数。

欧拉函数

$\mathrm{\Phi }(n)\backslash Phi(n)$表示小于等于$nn$的所有正整数中与$nn$互素的数的个数。显然如果我们$O(n)O(n)$的复杂度去遍历求解欧拉函数是不行的，它有一个更快的公式：

如果$n={\prod }_i{p}_i^{{\alpha }_i}n\; =\; \backslash prod\_i\; p\_i^\{\backslash alpha\_i\}$，其中$p_{i}p\_i$为质数，该式对于$nn$表示的是质因数分解，那么：

简单证明一下，记$nn$以内某个质数$p_{i}p\_i$的倍数的集合为$S_i=\lfloor \frac{n}{p_i}\rfloor S\_i\; =\; \backslash lfloor\; \backslash frac\{n\}\{p\_i\}\; \backslash rfloor$，目标就是找到它们的并集的大小$SS$，并将$nn$减去$SS$，就是$\mathrm{\Phi }(n)\backslash Phi(n)$。

根据集合论，其实$S=\sum S_i-\sum S_i\times S_j+\mathrm{.}\mathrm{.}\mathrm{.}+(-1{)}^{n-1}{S}_1\times \mathrm{.}\mathrm{.}\mathrm{.}\times S_{n}S\; =\; \backslash sum\; S\_i\; -\; \backslash sum\; S\_i\backslash times\; S\_j\; +\; ...\; +\; (-1)^\{n-1\}S\_1\; \backslash times\; ...\; \backslash times\; S\_n$，奇数相加、偶数相减。

如何找到$\frac{p}{q}\backslash frac\{p\}\{q\}$的循环节？

考虑$\frac{1}{q}\backslash frac\{1\}\{q\}$。

1. 如果$qq$的因子仅含有2或5，那么该小数是循环小数；
2. 如果不含2或5，10与$qq$互素，根据欧拉定理，$10^{\mathrm{\Phi }(q)}\equiv 1(modq)10^\{\backslash Phi(q)\}\; \backslash equiv\; 1(mod\backslash ;\; q)$，其中$\mathrm{\Phi }(q)\backslash Phi(q)$便是循环节，但不一定是最小的，因为最小的循环节重复k遍仍是循环节，所以通过遍历$\mathrm{\Phi }(q)\backslash Phi(q)$的因子找到最小的循环节即可。
3. 如果除了2和5还有其他的，先找出2和5的个数分别为a与b，循环节前面一段的长度便是$max(a,b)max(a,\; b)$，剩下的10与$\frac{q}{2^a{5}^b}\backslash frac\{q\}\{2^a5^b\}$互素，找到最小循环节即可。

import math
def phi(x: int) -> int:
    ans, i = x, 2
    while i * i <= x:
        if x % i == 0:
            ans = ans // i * (i - 1)
            while x % i == 0: x //= i 
        i += 1
    if x > 1: ans = ans // x * (x - 1)
    return ans

p, q = map(int, input().split())
g = math.gcd(p, q)
p //= g
q //= g # 化简
c2, c5 = 0, 0
while q % 2 == 0:
    q //= 2
    c2 += 1
while q % 5 == 0:
    q //= 5
    c5 += 1
if q == 1:
    print(-1)
    exit(0)
phiq = phi(q) # 拿到欧拉函数的值
ans, i = phiq, 2 # 找到最小的循环节
while i * i <= phiq:
    if phiq % i == 0: # 是因子
        if pow(10, i, q) == 1: ans = min(ans, i)
        if pow(10, phiq // i, q) == 1: ans = min(ans, phiq // i)
    i += 1
print(max(c2, c5), ans)

PS：涉及大整数的乘法、求模还是用python吧，用C++开到__int128才行。