该圆的方程是
$$(x-\frac{N}{2})^2+(y-\frac{N}{2})^2=\frac{N^2}{2},$$
即
$$(2x-N)^2+(2y-N)^2=2N^2.$$
等式右侧是偶数，因此$2x-N$、$2y-N$的奇偶性相同，且显然与N的奇偶性也相同。
因此$f(N)$就等于$a^2+b^2=n$的整数解的数量，其中$a=2x-N$、$b=2y-N$、$n=2N^2$。
正如已在第210题和第229题的解答中所提及的， 这是一个经典结论，若
$$n=2^{r}p_1^{s_1}\ldots p_j^{s_j}q_1^{t_1}\ldots q_k^{t_k},$$
是n的质因数分解，其中$p_1,\ldots, p_j$是模4余1型的素数，$q_1,\ldots, q_k$是模4余3型的素数，则只要$t_1,\ldots,t_k$中有一个奇数，解的数量就是0，而当$t_1,\ldots,t_k$全为偶数时，解的数量是
$$4(s_1+1)\ldots (s_j+1).$$
由于
$$420=4\times 3\times 5\times 7, $$
因此N可以有这样三种形式：$N=qp_1p_2^2p_3^3$、$N=qp_1^2p_2^{10}$、$N=qp_1^3p_2^{7}$，其中q是只有2和模4余3型素因子的数，而$p_1,p_2, p_3$都是模4余1型的素数（事实上还有例如$N=qp_1p_2^{17}$等情况，但容易验证过高的指数将使N不满足$N\le 10^{11}$的条件），且$q\le 10^{11}/(5^3\cdot13^2\cdot 17)$、$p_i\le10^{11}/(5^3\cdot13^2)$。
因此先用筛法找出符合条件的、模4余1型的素数，再使用这些素数筛选出满足要求的q，最后分别生成上述三种数并求和，最终结果是$271204031455541309$。
注：因计算量较大，代码中打印了进度信息。
m=10**11
m1=4733727
m3=278455
target=m1
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
p1=[k for k in range(2,target) if d[k]==0 and k%4==1]
print "prime list generated"
d=[0]*m3
i=0
while p1[i] < m3:
for n in range(p1[i],m3,p1[i]):
d[n]+=1
i+=1
q=[k for k in range(1,m3) if d[k]==0]
print "q list generated", len(q)
p=[]
for a in p1:
for b in p1:
if a!=b:
r=(a**3)*(b**7)
if r <= m:
p.append(r)
else:
break
print "type 1 completed"
for a in p1:
for b in p1:
if a!=b:
r=(a**2)*(b**10)
if r <= m:
p.append(r)
else:
break
print "type 2 completed"
for a in p1:
for b in p1:
if a*b*b*125>m:
break
else:
for c in p1:
if a!=b and b!=c and c!=a:
r=a*b*b*c*c*c
if r <= m:
p.append(r)
else:
break
print "type 3 completed"
p.sort()
print len(p)
s=0
for a in p:
for b in q:
r=a*b
if r <= m:
s+=r
else:
break
print s
|
