披萨馅料

你有一个被切成mn等分的圆形披萨，每一片披萨上都需要有恰好一份馅料。

共有m种不同的馅料($m\ge2$)，每种馅料都恰好可以放在n片披萨上($n\ge1$)，记$f(m,n)$为不同的馅料分配方案的总数（旋转后相同的方案视为同一种）。

可以验证，$f(2,1) = 1, f(2,2)=f(3,1)=2$，以及$f(3,2)=16$。其中$f(3,2)$的所有方案如下图：

求所有满足$f(m,n)\le10^{15}$的$f(m,n)$之和。

本题难度:

解答

根据此帖的内容有 $$f(m,n)=\frac{1}{mn}\sum_{d|n}\varphi(d)\frac{(\frac{mn}{d})!}{((\frac{n}{d})!)^m}=\frac{1}{mn}\sum_{d|n}\varphi(\frac{n}{d})\frac{(md)!}{(d!)^m}$$ 其中$\varphi$是欧拉Totient函数，d取遍n的所有约数。

因此先枚举n，对每个固定的n，从$m=2$开始枚举m，直到$f(m,n)$超过$10^{15}$为止。当$f(2,n)$也超过$10^{15}$时终止循环。

f增长非常快，很快就可得结果$1485776387445623$。

注：为减少代码量，以下使用了Sympy库来计算生成约数表并计算欧拉Totient函数，因此代码为Python 3。

from sympy import divisors
from sympy.ntheory.factor_ import totient
from math import factorial

bound=10**15

f=lambda m,n,dList,pList,fList:sum(pList[i]*factorial(m*dList[i])//fList[i]**m for i in range(len(dList)))//(m*n)

r=0
n=1
while True:
    dList=divisors(n)
    pList=[totient(n//d) for d in dList]
    fList=[factorial(d) for d in dList]
    m=2
    s=f(m,n,dList,pList,fList)
    if s>bound:
        break
    while s <= bound:
        r+=s
        m+=1
        s=f(m,n,dList,pList,fList)
    n+=1

print(r)