N的阶乘末尾0的个数（python）

您所在的位置：网站首页 › python用for求n的阶乘 › N的阶乘末尾0的个数（python）

N的阶乘末尾0的个数（python）

2024-02-08 04:35| 来源: 网络整理| 查看: 265

分析

对N的阶乘进行质因子分解，N! = ( $2^{X}\times 3^{Y}\times 5^{Z} \cdots$ )，由于 $10=2\times 5$ ，所以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 = i while j%5==0: res += 1 j //= 5 print(res) 解法 2

利用公式 $Z=[N/5] + [N/5^{2}] +[N/5^{3}] +\cdots$

其中[N/k]为1，2，3，..., N中能被k整除的数的个数

N = int(input()) res = 0 while N: res += N//5 N //= 5 print(res)

类似的问题：

求N的阶乘的二进制表示中最低位1的位置解法 1

这个和上面的解法类似，都是求1,2,..N中含2的质因子的个数，因为每乘一个2都会向左平移1位。

N = int(input()) res = 0 while N: N >>= 1 res += N print(res) 解法 2

N！含质因子2的个数等于N减去N的二进制中1的个数

N = int(input()) V = N res = 0 while V: V &= V-1 res += 1 print(N - res)

【本文地址】

N的阶乘末尾0的个数（python）

N的阶乘末尾0的个数（python）

今日新闻

推荐新闻

N的阶乘末尾0的个数 （python）

N的阶乘末尾0的个数 （python）

今日新闻

推荐新闻

N的阶乘末尾0的个数（python）

N的阶乘末尾0的个数（python）