Codechef练习问题需要帮助 - 在阶乘中找到尾随零

Question

我现在已经24小时工作,试图优化它.问题是如何在大约8秒内找到10000000和1000万个测试用例中的数字因子的尾随零的数量.

代码如下:

#include<iostream>

using namespace std;

int count5(int a){
    int b=0;
    for(int i=a;i>0;i=i/5){
        if(i%15625==0){
            b=b+6;
            i=i/15625;
        }
        if(i%3125==0){
            b=b+5;
            i=i/3125;
        }
        if(i%625==0){
            b=b+4;
            i=i/625;
        }
        if(i%125==0){
            b=b+3;
            i=i/125;
        }
        if(i%25==0){
            b=b+2;
            i=i/25;
        }
        if(i%5==0){
            b++;
        }
        else
            break;

    }
    return b;
}
int main(){
    int l;
    int n=0;
    cin>>l; //no of test cases taken as input
    int *T = new int[l];

    for(int i=0;i<l;i++)
        cin>>T[i]; //nos taken as input for the same no of test cases


    for(int i=0;i<l;i++){
        n=0;
        for(int j=5;j<=T[i];j=j+5){
            n+=count5(j); //no of trailing zeroes calculted 
        }
        cout<<n<<endl; //no for each trialing zero printed
    }

    delete []T;


}   

请通过建议一种新方法或建议对此方法进行一些修改来帮助我.

Answer 1

使用以下定理：

如果 p 是素数，则 p 的最高次方能整除 n！(n 阶乘) 为 [n/p] + [n/p^2] + [n/p^3] + ... + [n/p^k]，其中 k 是 p <= n 的最大幂，[x] 是 x 的整数部分。

参考资料：行星数学