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\)是这个等差数列的公差,则有:

$$ x^{2} -y^{2} -z^{2} =( a+d)^{2} -a^{2} -( a-d)^{2} =4ad-a^{2} =a( 4d-a)=n $$

则要使得题目中要求成立,需满足:

综合以上三个条件,我们有:

$$ 1< a< 10^{6} ,\ \frac{a}{4} < d< min\left( a,\frac{10^{6} +a^{2}}{4a}\right) $$

我们只需要在以上范围内遍历\(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])