135. 相同的差(Same differences)

已知正整数\(x,y,z\)构成等差数列，使得方程\(x^2-y^2-z^2=n\)有两个解的最小正整数\(n=27\)：

$$ 34^2 − 27^2 − 20^2 = 12^2 − 9^2 − 6^2 = 27 $$

已知使得方程有十个解的最小正整数\(n = 1155\)。在小于一百万的数中，有多少个\(n\)使得上述方程恰好有十个不同的解？

分析：既然\(x,y,z\)构成等差数列，我们可以令\(y=a,x=a+d,z=a-d\)，其中\(d\)是这个等差数列的公差，则有：

则要使得题目中要求成立，需满足：

• \(a,d\)必须为正整数且\((a-d)>0\)，则有\(d<a\)；
• \((4d-a)\)作为\(n\)的一个因子也必须要大于零，则有\((4d-a)>0\Rightarrow d>a/4\)；
• \(( 4d-a) a< 10^{6} \Rightarrow d< \frac{10^{6} +a^{2}}{4a}\)。

综合以上三个条件，我们有：

我们只需要在以上范围内遍历\(a\)与\(d\)，再计算\(a(4d-a)\)得到\(n\)，并累计出现不同的\(n\)的次数。遍历完成后，我们筛选出出现次数为十次的所有的\(n\)，统计他们的个数即为题目所求。代码如下：

# time cost = 1.21 s ± 5.8 ms

from collections import defaultdict

def main(N=10**6):
    res = defaultdict(int)
    for a in range(2,N+1):
        u = min(a,(N+a**2)//(4*a)+1)
        for d in range(a//4+1,u):
            res[a*(4*d-a)] += 1
    return len([k for k,v in res.items() if v==10])