三项式$(x+y+z)^{n}$的展开式中$x^ay^bz^c$项的系数是
$$\frac{n!}{a!b!c!}=\binom{n}{a}\binom{n-a}{b}.$$
因此先令k从2取到200000，缓存$k!$的质因数分解中2和5的次数。
接下来不妨设$a\le b \le c$，取a从0到$200000/3$：
若$\binom{n}{a}$已能被$10^{12}$整除，则直接统计（实际计算结果显示不存在这样的情况）。
若$\binom{n}{a}(n-a)!$中2和5的次数都小于12，则$10^{12}$必定不能整除$\frac{n!}{a!b!c!}$，也无需再作计算（在a充分大时能跳过不少循环）。
对其它情形则再令b从a取到$(n-a)/2$并根据缓存的$k!$统计。
最后结果是$479742450$。
n=200000
p=[1 << k for k in range(19)]
q=[5**k for k in range(9)]
u=[0]*(n+1)
v=[0]*(n+1)
for k in range(2,n+1,2):
i=0
while k%p[i]==0:
i+=1
u[k]=i-1
for k in range(5,n+1,5):
i=0
while k%q[i]==0:
i+=1
v[k]=i-1
for k in range(1,n+1):
u[k]=u[k-1]+u[k]
v[k]=v[k-1]+v[k]
r=0
for a in range(n/3+1):
if u[n]-u[a]-u[n-a]>=12 and v[n]-v[a]-v[n-a]>=12:
if (n-a)%2==0:
r+=((n-a)/2-a)*6
else:
r+=((n-a)/2-a)*6+3
print a, ((n-a)/2-a)*6 if (n-a)%2==0 else ((n-a)/2-a)*6+3
elif u[n]-u[a]>=12 and v[n]-v[a]>=12:
for b in range(a,(n-a)/2+1):
c=n-a-b
if u[n]-u[a]-u[b]-u[c]>=12 and v[n]-v[a]-v[b]-v[c]>=12:
if a==b or b==c:
r+=3
else:
r+=6
if a%1000==0: print a
print r
|
