唯一的差

已知正整数x、y、z构成等差数列。

取$n=20$，则方程$x^2−y^2−z^2=n$只有唯一的一组解： $$13^2−10^2−7^2=27.$$ 在小于一百的数中，有25个n能使该方程只有唯一解。

在小于五千万的数中，有多少个n能使方程有唯一解？

本题难度:

解答

采用与第135题完全相同的策略，不过由于此处的上界很大，用筛法会占用很多空间，因此改为直接遍可能的a和d的取值并保留对应的唯一n。结果是$2544559$。

target=50000000

s={}

for a in range(2,target):
    d=a/4+1
    n=a*(4*d-a)
    while d < a and n < target:
        s[n]=s.get(n,0)+1
        d+=1
        n=a*(4*d-a)

print sum(s[i]==1 for i in s)