0274 整除性乘数
* * * *
拉格朗日计划
* * * *
整除性乘数

给定正整数m,n,设$n=10a+b$,其中b是个位数,定义 $$f_m(n)=a+mb.$$ 给定任意与10互质且大于1的正整数p,其整除性乘数$m_p$是一个小于p,且满足$f_{m_p}(n)$能被p整除当且仅当n能被p整除的正整数。

(显然当n远大于p时,迭代计算$f(f(\ldots f(n)\ldots))$是一种能快速检验p整除性的方法)

例如,113的整除性乘数是34。$f(76275)=7627+5\cdot34=7797$,而76275和7797都能被113整除。$f(12345)=1234+5\cdot 34=1404$,12345和1404都不能被113整除。

可以验证对于所有小于1000且与10互质的素数,其整除性乘数之和是39517。

求对于所有小于$10^7$且与10互质的素数的整除性乘数之和。

本题难度:



解答

因p与10互质,因此显然$f_{m_p}(n)$与$10f_{m_p}(n)=10a+10m_pb$对于p的整除性相同。

此处可以作更强的构造:存在$m_p$,使得$10f_{m_p}(n)$和n模p同余,即 $$10f_{m_p}(n)-n=10bm_p-b=(10m_p-1)b=0 \pmod p,$$ 亦即 $$10m_p=1\pmod p$$ 由费马小定理可得 $$m_p=10^{p-2} \bmod p$$ 就是满足要求的数。

先用筛法找出满足要求的素数,直接用内建函数计算$m_p$汇总即得结果$1601912348822$。

target=10000000
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

print 39517+sum(pow(10,k-2,k) for k in range(1001,target) if d[k]==0)