POJ 1401 Factorial

题意很好理解,给定一个N数,求N!末尾有多少个连续0?

我们知道,一个数的阶乘中含有一个10(20,30,40.。。。)都可以再末尾增加一个0,存在一个2*5,4*15.。。。也可以增加一个0;也就是说,从5开始,凡是遇到5,10,15,20,25,30,35。。。。都要增加一个0.至于5需要一个偶数来乘,偶数比5多得多,就不用考虑够不够乘的问题了。

但是其中有一点很关键。就是类似于25,125,625这些数。

注意观察发现25=5*5,125=5*5*5,625=5*5*5*5;也就是说,25能拆分成2个5来和偶数乘,故而能产生2个0,125能产生3个0,625产生4个。。。。。

所以算法就有了,如下:

 

#include <iostream>

using namespace std;//这道题的意思就是你让一个数做阶乘,最后有多少个0

int main() {

    int m,a;

    cin>>m;

    for(int i=0;i<m;i++)

    {

        int sum=0;

        cin>>a;

       while(a)

       {

           sum+=a/5;

           a=a/5;

       }

        cout<<sum<<endl;

    }

    return 0;

}

原文地址:https://www.cnblogs.com/guohaoyu110/p/6343508.html