末尾的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的个数。

#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;
}

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。  

代码实现  

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 小助理，如未能正确解答您的问题，请继续追问。