先上代码
n = int(input())
k = 5
res = 0
while k <= n :
res += n // k
k *= 5
print(res)
代码看起来很简单,但这个代码和原题看起来似乎没太大联系。没关系请接着看:
基础
题目要求我们求的是n阶乘末尾0的个数,是个人都能想到最基础的解法是看n包含2的多少次幂和5的多少次幂,即$2^{m1}5^{m2}$ ,答案为min(m1,m2),但这样写会超时。
优化
仔细观察
min(m1,m2)=m2是永远成立的,这个可以自行证明,不是很难。直观理解便是对于幂相同时,底数为2的一定早于底数为5的产生。推翻这个结论就像推翻2小于5一样
所以其实我们只需看n!包含了5的多少次幂
接下来证明:
$$n/5 + n/5^2 + … = m2$$
该式也就是上面代码的意义:
因为底数为5,m2一定是由那些可以被5的幂次方整除的数贡献的,我们将仅仅能被5的k次方整除的数的个数记为$c(k)$那么我们可以有一个原始的公式
$$m2 = c(1) + c(2) * 2 + c(3) * 3 + … $$
整理可得:
$$m2 = [c(1) + c(2) + c(3)] + [c(2) + c(3) + …] + …$$
每个大括号的值即为n/5, n/25, n/125, …