0360 可怕的球面
* * * *
拉格朗日计划
* * * *
可怕的球面

三维空间中的两点$(x,y,z)$和$(x',y',z')$间的曼哈顿距离是$|x-x'|+|y-y'|+|z-z'|$。

记$C(r)$为球心在原点且半径为r的球体,$I(r)$为$C(r)$表面所有坐标为整数的点构成的集合。

再记$S(r)$为$I(r)$中所有元素到原点的曼哈顿距离之和,例如$S(45)=34518$。

求$S(10^{10})$。

本题难度:



解答

本题用到勾股四元组的生成公式。若$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)