本题用到勾股四元组的生成公式。若$x^2+y^2+z^2=r^2$,那么与勾股数的情况类似,所有满足要求的整数四元组可由
\begin{align*}
x&=a^2+b^-c^2-d^2 \\
y&=2(ad+bc) \\
z&=2(bd-ac) \\
r&=a^2+b^2+c^2+d^2 \\
\end{align*}
此外,由于$10^{20}$能被4整除,而两个奇数的平方和模4余2,因此$x,y,z$必定都能被$2^{10}$整除。
取$r=5^{10}$并枚举a,b,c,d,生成x,y,z后去重,再考虑x,y,z的全排列以及正负号,最后汇总即可得最终结果$878825614395267072$。
注:因用到Walrus算符(即:=)以及fstring等新特性,以下代码为Python 3。未打印进度信息,运行时间约为数分钟。
target=5**10
bound=5**5
scaling=1 << 10
T={}
for a in range(bound+1):
for b in range(bound+1):
if (c:=a*a+b*b) < target:
if c in T:
T[c].add((a,b))
else:
T[c]={(a,b)}
S=set()
for n in T:
for a,b in T[n]:
if (m:=target-n) in T:
for c,d in T[m]:
S.add(tuple(sorted([abs(a*a+b*b-c*c-d*d),2*(a*d+b*c),2*abs(b*d-a*c)])))
print(sum((x+y+z)*(6 if y==0 else (24 if x==y or y==z or x==0 else 48)) for x,y,z in S)*scaling)
|