将原方程写做
$$\frac{1}{ap}+\frac{1}{bp}=\frac{1}{10^n},$$
则根据第108题和第110题的分析有
$$ap=10^n+x,\quad bp=10^n+y,$$
其中
$$10^{2n}=xy.$$
因此找出$10^{2n}$的约数对$x,y$，并计算
$$d=\gcd(10^n+x,10^n+y).$$
d的每个约数都可以作为p。
用筛法生成不超过45000的素数以计算d的约数的个数，汇总后即得结果$53490$。
import math
target=45000
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
p=[k for k in range(2,target) if d[k]==0]
r=0
for n in range(1,10):
m=10**n
m2=m*m
for i in range(2*n+1):
for j in range(2*n+1):
x=(5**i)<< j
y=m2//x
if x<=y:
d=math.gcd(m+x,m+y)
k=1
u=0
while u < len(p) and d>1 and d>=p[u]:
if d%p[u]==0:
z=0
while d%p[u]==0:
d//=p[u]
z+=1
k*=(z+1)
u+=1
if d>1:
k*=2
r+=k
print(n,r)
print(r)
|
