分子为$1$的分数称为单位分数。分母为$2$到$10$的单位分数的十进制表示如下：

\begin{align*} 1/2 &= 0.5 \\ 1/3 &= 0.(3) \\ 1/4 &= 0.25 \\ 1/5 &= 0.2 \\ 1/6 &= 0.1(6) \\ 1/7 &= 0.(142857) \\ 1/8 &= 0.125 \\ 1/9 &= 0.(1) \\ 1/10 &= 0.1 \\ \end{align*} 其中括号表示循环节。例如$0.1(6)$表示$0.1666666\ldots$，其循环节的长度为$1$。可以看出$1/7$的循环节长度为$6$。

分母的质因数只含2和5的单位分数是有限小数，其循环节长度为0。

记$L(n)$为单位分数$1/n$的循环节长度，可以验证$\sum_{n=3}^{10^6}L(n)=55535191115$。

求$\sum_{n=3}^{10^8}L(n)$。

本题难度:

解答

由第26题的分析可知若$n=2^a5^bm$，其中m与2和5都互素，那么$L(n)$就是10在模m乘法群中的阶，直接遍历计算即可得结果$446572970925740$。

注1：以下代码使用sympy库的n\_order方法计算10在模m乘法群中的阶，并用cache装饰器作记忆化搜索，因此为Python 3代码，且其中打印了进度信息。

注2：本题数据量很大，上述方法需要数个小时。为提升效率，可以使用筛法作质因数，再利用$L(n)$的乘法性质：$L(n)$等于n的各素幂因子的循环节长度的最小公倍数、以及对大多数素数而言（在本题数据范围内除3、487、56598313以外的素数都满足）有$L(p^k)=pL(p^{k-1})$这一性质，不过码量较大，此处未选择这样的做法。

注3：以下代码可以压缩到两行，但由于运行时间很长，压缩后不利于观察进度，因此略显罗嗦。

from sympy import n_order
from functools import *

tick=10**6

@cache
def f(x):
    return n_order(10,x)

s=0
for n in range(3,10**8+1):
    m=n
    while m%5==0:
        m//=5
    while m%2==0:
        m//=2
    if m>1:
        s+=f(m)
    if n%tick==0:
        print(n//tick,"percent completed, current sum:",s)

print(s)