末尾的0
题目描述写一个程序，求N的阶乘（N!=1*2*3...N），求末尾0的个数。例如： 12! = 1*2*3*4...11*12=479001600末尾有2个0。所以输出2
输入描述
一个整数 N。
输出描述
N!末尾 0 的个数
样例1
输入
12
输出
2
对于 20%的数据有 $0<N<=15$对于 100% 的数据有 $0<N<=10000$
分析：一个数末尾有几个0，取决于它的质因数乘积形式有几个5和几个2，这两个数量的最小值就是0的个数。
#include<bits/stdc++.h>
using namespace std;
int countfactor(int a, int b){
int cnt=0;
while(a%b==0){
a/=b;
cnt+=1;
}
return cnt;
}
int main(){
int n;
cin>>n;
int twos=0,fives=0;
for(int i=1;i<=n;++i){
int two=countfactor(i,2);
int five=countfactor(i,5);
twos+=two;
fives+=five;
}
cout<<min(twos, fives);
return 0;
} 解题思路
计算N!（N的阶乘）末尾0的个数，本质上是计算N!中因子10的个数。而10可以分解为2和5的乘积，在阶乘中2的个数远多于5的个数，因此问题转化为计算N!中因子5的个数。
计算方法如下：
1. 计算N中能被5整除的数的个数，即 。
2. 计算N中能被25整除的数的个数，即 （因为每个25提供额外的一个5因子）。
3. 计算N中能被125整除的数的个数，即 ，依此类推，直到N/5^k=0。
代码实现
python
def count_trailing_zeros(n):
count = 0
while n >= 5:
n //= 5
count += n
return count
# 读取输入
n = int(input().strip())
print(count_trailing_zeros(n))
复杂度分析
该算法的时间复杂度为 O(log N)，因为每次循环 n 都会除以 5，减少规模，因此效率很高。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]