分析
对N的阶乘进行质因子分解,N! = (),由于,所以0的个数只与X和Z有关,每一对2和5相乘可以得到一个10,于是有0的个数等于min(X,Z),不难看出X大于Z。所以0的个数只与Z有关。
解法 1
要计算Z,最直接的方法就是计算i(i=1,2,..N)的因式分解中5的指数,然后求和:
N = int(input())
res = 0
for i in range(1,N+1):j = iwhile j%5==0:res += 1j //= 5
print(res)
解法 2
利用公式
其中[N/k]为1,2,3,..., N中能被k整除的数的个数
N = int(input())
res = 0
while N:res += N//5N //= 5
print(res)
类似的问题:
求N的阶乘的二进制表示中最低位1的位置
解法 1
这个和上面的解法类似,都是求1,2,..N中含2的质因子的个数,因为每乘一个2都会向左平移1位。
N = int(input())
res = 0
while N:N >>= 1res += N
print(res)
解法 2
N!含质因子2的个数等于N减去N的二进制中1的个数
N = int(input())
V = N
res = 0
while V:V &= V-1res += 1
print(N - res)