只包含数字1的数称为全一数，记$R(k)$为长度为k的全一数，例如$R(6)=111111$。

考虑形如$R(10^n)$的全一数。尽管$R(10)$、$R(100)$和$R(1000)$都不能被17整除，$R(10000)$却能够被17整除。然而，不存在使得$R(10^n)$能被19整除的n。事实上，在小于100的质数中，只有11、17、41和73能够成为某些$R(10^n)$的质因数。

找出所有小于十万且不会成为任何$R(10^n)$的质因数的质数之和。

本题难度:

解答

令m为10在模p乘法群中的阶数（即最小的、满足$10^m$模p余1的数），与第132题的分析类似，若p是这样的素数，则m不能整除任何$10^n$，从而m应当有不等于2或5的质因数。

生成十万以下所有形如$2^a5^b$的数，再一一检查其能否成为m，排除相应的素数后剩余的就是满足要求的素数，结果是$453647705$。

target=100000
d=[0]*target
n=2

while n < target:
    for i in range(n+n,target,n):
        d[i]=d[i]+1
    n=n+1
    while n < target and d[n]>0:
        n=n+1

primeList=[k for k in range(2,target) if d[k]==0]
d=sorted([k for i in range(17) for j in range(8) for k in [(2**i)*(5**j)] if k<=target and k>1])

def bigMod(k,p):
    if k < 10:
        return (10**k)%p
    else:
        return (bigMod(k/2,p)*bigMod(k-k/2,p))%p

r=[]
for p in primeList:
    i=1
    while d[i]<=p-1 and ((p-1)%d[i]!=0 or bigMod(d[i],p)!=1):
        i+=1
    if d[i]>p-1:
        r.append(p)
print sum(r)