阶乘新问题 O(n)解法

解题思路: 

1. 阶乘的结果有0，只能是5和偶数2，4，6，8。。相乘产生，即有一个5则必有一个0。最后有多少个0化为计数有多少个5的问题。

2. 5以上的数字阶乘，逢5则多一个0，于是可以5为步长计数。若采用累加的直观办法，会超时，则必然要用通项公式计算。观察可得(n-i+1)*1。

   
   

3. 注意到如果有25，与4，8。。相乘，会产生两个0，所以上述通项公式也适用于>=25的数字，要每逢25再加一次(n-i+1)。

4. 同理，>=125的，每逢125再加一次(n-i+1)。。。。。。

5. >=5^x，每逢5^x再加一次(n-i+1)，直到5^x>n，循环结束。

循环次数：n/5+n/25+n/125+....+1。时间复杂度O(n)。

参考代码:

#include #include int main()
{
    int i=1;
    unsigned long long near,x=0,f=1,n;
    scanf("%lld",&n);
    while(n>f){
        f=pow(5,i);
        if(n0){
            x+=n-near +1;
            near-=f;
        }
        i++;
    }
    printf("%lld",x);
}