欲使$c/a$最小,这三个数应该充分接近。因此选定一个范围$(\sqrt[3]{43!}-\epsilon, \sqrt[3]{43!})$,在此范围内从大到小枚举$43!$的约数作为a,选定a以后b一定是$43!/a$的不超过$\sqrt{43!/a}$的最大约数。
因此需要一个方法$f(n,t)$,返回不超过t的n的最大约数,反复迭代f,就可以枚举a(实际只需十多次即可),再调用f来生成b,实际实现中直接用字典形式的n的质因数分解作为第一个参数,初始分解为:
$$43!=2^{39}\times3^{19}\times5^9\times7^6\times11^3\times13^3\times17^2\times19^2\times23\times29\times31\times37\times41\times43.$$
最终结果是$1177163565297340320$,此时a,b,c分别等于392386762388275200, 392388272221065120, 392388530688000000。
import math
d={2:39,3:19,5:9,7:6,11:3,13:3,17:2,19:2,23:1,29:1,31:1,37:1,41:1,43:1}
n=math.factorial(43)
m=int(n**(1/3))+1
def f(D,target):
A=[1]
B=[1]
for p,k in D.items():
if len(A) < len(B):
A.extend([p**(y+1)*x for y in range(k) for x in A])
else:
B.extend([p**(y+1)*x for y in range(k) for x in B])
A.sort()
B.sort(reverse=True)
y=z=0
for x in A:
while y < len(B) and x*B[y]>target:
y+=1
if y>=len(B):
break
z=max(z,x*B[y])
return z
a=f(d,m)
mc=n
ma=mb=1
r=0
for i in range(20):
m=n//a
d2={}
for p in d.keys():
k=0
t=m
while t%p==0:
t//=p
k+=1
if k>0:
d2[p]=k
b=f(d2,int(math.sqrt(m))+1)
c=m//b
if a <= b <= c and c*ma < mc*a:
ma,mb,mc=a,b,c
r=a+b+c
a=f(d,a-1)
print("answer:",r,"attained at a,b,c=",ma,mb,mc)
|