记$d=\gcd(x,y)$，$x=ad,y=bd$，则有
$$p(a^2-ab+b^2)=d(a^2+b^2)(a-b).$$
可以验证，$\gcd(a^2-ab+b^2,(a^2+b^2)(a-b))=1$。
若不然，设q是一能整除$\gcd(a^2-ab+b^2,(a^2+b^2)(a-b))$的素数，则q至少能整除$a^2+b^2$或$a-b$中的一项。
若q能整除$a-b$，则由它也能整除$a^2-ab+b^2=a(a-b)+b^2$可得q也能整除b，从而也能整除$a=a-b+b$，这与$\gcd(a,b)=1$矛盾。
若q能整除$a^2+b^2$，则由它也能整除$a^2-ab+b^2=(a^2+b^2)-ab$可得q也能整除$ab$，即q能整除a或b，不论何者结合q能整除$a^2+b^2$都看得q能同时整除$a,b$，从而与$\gcd(a,b)=1$矛盾。
由以上分析可知$(a^2+b^2)(a-b)$能整除p，但p是素数，因此有
$$p=(a^2+b^2)(a-b),$$
从而$a-b=1$且
$$p=a^2+b^2=b^2+(b+1)^2=2b^2+2b+1,$$
由于本题数据量很大，直接枚举b并对$2b^2+2b+1$作素性检验的效率比较低。注意到
$$2(kp+n)^2+2(kp+n)+1=2k^2p^2+4nkp+2kp+2n^2+2n+1=2n^2+2n+1\pmod p$$
以及
$$2(kp-n-1)^2+2(kp-n-1)+1=2k^2p^2-4(n+1)kp+2kp+2n^2+2n+1=2n^2+2n+1\pmod p$$
因此只要p能整除$f(n)=2n^2+2n+1$，就也能整除$f(kp+n)$和$f(kp-n-1)$，从而用与第216题类似的方法可得结果$4037526$。
注：为防卡死，以下为Python 3代码且打印了进度信息。
bound=5000000000000000
target=50000000
f=[2*b*b+2*b+1 for b in range(target)]
tick=target//100
tick2=100
r=0
for n in range(1,target):
p=f[n]
if p==2*n*n+2*n+1:
r+=1
if p>1:
for q in range(p+n,target,p):
while f[q]%p==0:
f[q]//=p
for q in range(p-n-1,target,p):
if q>0:
while f[q]%p==0:
f[q]//=p
if n<=tick2:
print(n,"completed,current r",r)
elif n<=tick:
if n%(tick2)==0:
print(n//tick2,"hundred completed, current r:",r)
elif n%tick==0:
print (n//tick,"percent completed, current r:",r)
print(r)
|
