记三边长为$a < b < c$，外接圆半径为r，s为三角形面积，则本题有几种不同的解法：
一是可以利用$r=abc/(4s)$，从而用与第283题相似的方法枚举并检验各边长和面积为有理数的三角形。
二是可以利用外心是三边中垂线的交点，推出r与$a/2,b/2,c/2$中的任意两项都形成勾股数，从而枚举并检验勾股三元组。
不过在官方论坛上提供了这样一个更直接的公式，即若
$$r=p_1^{e_1}\ldots p_k^{e_k}q$$
是的质因数分解，其中$p_1,\ldots, p_k$都是模4余1型素数，而q是其他类型素幂的乘积，则满足要求的、以r为外接圆半径的三角形数量是
$$\frac{1}{6}\left(2\prod_{i=1}^k(3e_i^2+3e_i+1)-3\prod_{i=1}^k(2e_i+1)+3\prod_{i=1}^k(2\lfloor \frac{e_i}{2}\rfloor+1)-2\right)$$
用筛法求出所有数的质因数分解后汇总求和即得结果$727227472448913$。
注：因用math.prod函数以及cache装饰器作记忆化搜索，以下代码为Python 3。
from functools import *
import math
@cache
def R(shapes):return (2*math.prod(3*e*e+3*e+1 for e in shapes)-3*math.prod(2*e+1 for e in shapes)+3*math.prod(2*(e>>1)+1 for e in shapes)-2)//6
target=10**7+1
d=[0]*target
n=2
while n < target:
for i in range(n*n,target,n):
d[i]=d[i]+1
n=n+1
while n < target and d[n]>0:
n=n+1
shapes=[[] for _ in range(target)]
for p in range(3,target):
if d[p]==0 and p%4==1:
for q in range(p,target,p):
e=0
r=q
while r%p==0:
r//=p
e+=1
shapes[q].append(e)
print(sum(k*R(tuple(sorted(shapes[k]))) for k in range(1,target)))
|
