129. 循环单位数整除性(Repunit divisibility)

只包含数字\(1\)的数被称为循环单位数，定义\(R(k)\)是长为\(k\)的循环单位数，如\(R(6)=111111\)。如果\(n\)是一个整数且\(gcd(n,10)=1\)，可以验证总是存在\(k\)使得\(R(k)\)能够被\(n\)整除，记\(A(n)\)是这些\(k\)中最小的一个，则有\(A(7)=6,A(41)=5\)。易知使得\(A(n)\)第一次超过十的\(n\)是\(17\)，求使得\(A(n)\)第一次超过一百万的\(n\)。

分析：题目中说"可以验证总是存在\(k\)使得\(R(k)\)能够被\(n\)整除"，我们首先来看看这个判断为什么是正确的，在分析的过程中我们也可以得到解题的一些关键线索。

对于\(R_1,R_2\cdots,R_i,\cdots R_j,\cdots R_n\)，假设其都不整除\(n\)，则这些循环单位数模\(n\)的结果必然都落在\([1,n-1]\)，然而共有\(n\)个循环单位数，则根据抽屉原理，必有\(i,j\)满足\(1\le i\le j\le n\)使得其模\(n\)的结果相同，即：

而\((R_j-R_i)\)即为一个前\((j-i)\)位数字都为一而后\(i\)位数字都为零的数，即

因\(gcd(10,n)=1\)，则有\(R_{j-i}\equiv0\pmod{n}\)，即一个位数在\([1,n]\)间的循环单位数可以整除\(n\)，和我们的假设矛盾，所以在\(R_1\)至\(R_n\)间总存一个循环单位数可以整除\(n\)。同时易知满足题目条件的\(A(n)\le n\)。因此要使得\(A(n)>10^6\)，则\(n\)也必须大于\(10^6\)，我们只需要从一百万向上搜索即可。

根据循环单位数的定义易知\(R_{k} =\frac{10^{k} -1}{9}\)，如果其整除\(n\)，则有：

根据右式我们要求满足条件的最小的正整数\(k\)，而这正是阶数的定义，我们可以使用\(sympy\)中相关的数论函数来求解。同时根据之前的推理，我们只需要从一百万向上搜寻即可，找到的第一个使得\(k\)大于一百万的\(n\)即为题目所求。此外因为\(gcd(n,10)=1\)，则\(n\)必是一个奇数同时不整除五，这样可以进一步减少搜索空间。代码如下：

# time cost = 642 µs ± 2.22 µs

from sympy.ntheory import n_order

def main(N=10**6):
    n = N + 1
    while True:
        if n % 5 != 0 and n_order(10,9*n)>N:
            return n
        else:
            n = n + 2