题解 | #阶乘末尾非零数字#

众所周知，末尾有多少个连续0，相信大家都会求，就是统计2和5的个数，那么连续0的个数也就为。

那么这道题我们只需要统计一下2和5的个数，然后将其他所有数乘起来，每次模10，最后补上剩余的2的个数。

让我们来分析一下时间复杂度，大概应该是，对于，按道理不能过呀，为什么跑的这么快呢？63ms就过了！！！

看一下代码：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    int ans=1;
    int c2=0,c5=0;
    for(int i=1;i<=n;i++){
        int x=i;
        while(x%2==0){
            c2++;
            x/=2;
        }
        while(x%5==0){
            c5++;
            x/=5;
        }
        ans=ans*x%10;
    }
    for(int i=0;i<c2-c5;i++) ans=ans*2%10;
    cout << ans << endl;
}
/*

*/
// 64 位输出请用 printf("%lld")

我们看一下被加了多少次，根据勒让德定理，质数的指数为，那么根据这个公式可以算出分别被计算的次数为和，那么总时间复杂度为，所以这就是跑的很快的原因。