以下解法来自官方论坛，本题似乎应当有更深刻的解法。
设两交点A和B分别在原点和$(a,b)$，则$\gcd(a,b)=1$，否则连线段上就有整点，再考虑该线段的中点可知a,b同为奇数。
简单计算可以发现任何过A和B的圆的圆心都在直线$(a/2,b/2)+(t+1/2)(b,-a)$上，其中$t\in\mathbb Z$是参数，对应的半径是$r^2=(a^2+b^2)(t^2+(t+1)^2)/2$。
过AB的直线将平面分成两部分，一部分H包含圆心，另一部分H'包含透镜，要满足题意，圆中的整点需要都在H内。
枚举$a,b$，并枚举交线中点$(a/2,b/2)$附近的整点，可得$t$的下界，其上界显然。
如此则每组$(a,b)$都有一系列符合要求的半径，两两组合（只需将圆心分别放置在AB两侧即可。不过因对称性枚举时只需考虑圆心在一侧的情况）后去重即得结果$4884650818$。
注：以下代码改编自官方论坛，因math.ceil只在Python 3返回整型，因此代码为Python 3。
import math
bound=100000
class line(object) :
def __init__(self,P0,P1) :
try:
self.m=float(P1)
except:
self.m=(P1[1]-P0[1])/(P1[0]-P0[0])
self.n=P0[1]-self.m*P0[0]
perp=lambda g,P0:line(P0,-1/g.m)
perp2=lambda P0,P1:perp(line(P0,P1),((P0[0]+P1[0])/2,(P0[1]+P1[1])/2))
cap=lambda g1,g2:((g2.n-g1.n)/(g1.m-g2.m),g1.m*(g2.n-g1.n)/(g1.m-g2.m)+g1.n)
def getCandidate(a,b):
g=perp2((0,0),(a,b))
xmax=0.5
for x in range(1,a) :
y=(b*x)//a
if y!=0:
if a*y==b*x :
return []
g1=perp2((0,0),(x,y))
P=cap(g,g1)
xmax=min(P[0],xmax)
t=math.ceil((a/2-xmax)/b-0.5)
res=[]
while True:
x=(a-b)//2-t*b
y=(b+a)//2+t*a
r2=x*x+y*y
if r2>bound*bound :
return res
res.append(r2)
t+=1
candidates=[]
a=1
finished=False
while a < bound and not finished:
for b in range(1,a+1,2):
r=set(getCandidate(a,b))
if r:
candidates.append(r)
elif b==1:
finished=True
a+=2
check=lambda s,m,p: m*len(s)*(len(s)+1)//2+sum(check(s & candidates[i],-m,i+1) for i in range(p,len(candidates))) if len(s)>0 else 0
print(sum(check(j,1,i+1) for i,j in enumerate(candidates)))
|
