令k为$p_1$的位数，并记$m=10^k$，需要找到最小的、满足
$$n\equiv 0 \pmod{p_2}, \quad n\equiv p_1 \pmod m.$$
由中国剩余定理可知上式存在形如$n=xp_1p_2$的解，那么最小的n显然就是$xp_1p_2$模$p_2m$的余数。 注意到若把$xp_1p_2$写成
$$xp_1p_2=am+p_1,$$
的形式，那么a需要能被$p_1$整除，从而上式可以进一步简化为
$$xp_2-ym=1,$$
其中$y=a/p_1$，这是一个标准的线性丢番图方程，有解的前提是$\gcd(p_2,m)=1$，此时逆用辗转相除法即可求出x，结果是$18613426663617118$。
target=1000000
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(5,target) if d[k]==0]+[1000003]
n=len(primeList)
#return d,x,y where d=gcd(a,b); ax+by=d with x,y being one of the two pairs satisfying |x|<=y/d,|y|<=x/d
def bezout(a,b,xa=1,ya=0,xb=0,yb=1):
r=a%b
q=a//b
if r==0:
return b,xb,yb
else:
return bezout(b,r,xb,yb,xa-q*xb,ya-q*yb)
s=0
for i in range(n-1):
p,q=primeList[i],primeList[i+1]
m=10**len(str(p))
x=bezout(q,m)[1]
s+=(x*p*q)%(q*m)
print s
|
