末尾的0

player-none

题目描述
写一个程序，求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的个数。

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int countfactor(int a, int b){
   
4.     int cnt=0;
   
5.     while(a%b==0){
   
6.         a/=b;
   
7.         cnt+=1;
   
8.     }
   
9.     return cnt;
   
10. }
    
11. int main(){
    
12.     int n;
    
13.     cin>>n;
    
14.     int twos=0,fives=0;
    
15.     for(int i=1;i<=n;++i){
    
16.         int two=countfactor(i,2);
    
17.         int five=countfactor(i,5);
    
18.         twos+=two;
    
19.         fives+=five;
    
20.     }
    
21.     cout<<min(twos, fives);
    
22.     return 0;
    
23. }

复制代码

FishC

解题思路  

计算N!（N的阶乘）末尾0的个数，本质上是计算N!中因子10的个数。而10可以分解为2和5的乘积，在阶乘中2的个数远多于5的个数，因此问题转化为计算N!中因子5的个数。  

计算方法如下：  
1. 计算N中能被5整除的数的个数，即 [N/5]。  
2. 计算N中能被25整除的数的个数，即 [N/25]（因为每个25提供额外的一个5因子）。  
3. 计算N中能被125整除的数的个数，即 [N/125]，依此类推，直到N/5^k=0。  

代码实现  

1. python
   
2. def count_trailing_zeros(n):
   
3.     count = 0
   
4.     while n >= 5:
   
5.         n //= 5
   
6.         count += n
   
7.     return count
   
8. 
   
9. # 读取输入
   
10. n = int(input().strip())
    
11. print(count_trailing_zeros(n))
    

复制代码

复杂度分析  
该算法的时间复杂度为 O(log N)，因为每次循环 n 都会除以 5，减少规模，因此效率很高。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。