0418 因数三元组
* * * *
拉格朗日计划
* * * *
因数三元组

若$a,b,c,n\in\mathbb N$满足$n=abc$以及$1\le a\le b\le c$,就称$(a,b,c)$为n的因数三元组。

在n的所有因数三元组$(a, b, c)$中,取使得$c/a$最小的一组,可以验证这样的三元组总是唯一的,并记$f(n)$为该组的和。

例如$f(165)=19, f(100100) = 142, f(20!)=4034872$。

求$f(43!)$。

本题难度:



解答

欲使$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)