本题就算法而言很简单，即meet in the middle法。
先遍历k，生成所有不超过$\pi$的$f_n(k)$，并将这些值保存在列表f中。
再遍历f，保存所有不超过$\pi$的$f_n(i)+f_n(j)$的值在列表g中，并将g排序。
最后遍历g，对其中每一值，二分查找表中令一项，使两者之和最接近$\pi$。
本题的主要性能瓶颈在于空间，因列表g有近八千万项，因此难以同时保存$i^2+j^2$的值，需要在找出最值后再双循环遍历一次f以获得对应的i,j。
最终结果是159820276，相应的a,b,c,d分别是1433, 2147, 4903, 1136。
注：为优化内存使用，以下代码为Python 3，用时若干分钟，需耐心等待。
import math,bisect
n=10000
f=[]
k=0
while (t:=(math.exp(k/n)-1))<=math.pi:
f.append(t)
k+=1
print(f"length of f is {len(f)}")
g=[f[i]+f[j] for i in range(len(f)) for j in range(i,len(f)) if f[i]+f[j]<=math.pi]
g.sort()
print(f"length of f+f is {len(g)}")
i=0
j=len(g)
m=math.pi
mi=i
mj=j
while i < len(g) and i <= j:
j=bisect.bisect(g,math.pi-g[i])
if j < len(g) and 0 <= g[i]+g[j]-math.pi < m:
m=g[i]+g[j]-math.pi
mi=i
mj=j
j-=1
if j>=0 and 0 < math.pi-g[i]-g[j] < m:
m=math.pi-g[i]-g[j]
mi=i
mj=j
i+=1
d=[(i,j,i*i+j*j) for i in range(len(f)) for j in range(i,len(f)) if f[i]+f[j]==g[mi] or f[i]+f[j]==g[mj]]
print("a,b,c,d=",d[0][0],d[0][1],d[1][0],d[1][1])
print(d[0][2]+d[1][2])
|
