Contents

1. 1. 题目：
2. 2. 分析：
   1. 2.1. 版本一：
   2. 2.2. 版本二：
   3. 2.3. 版本三：

题目：

输入n，求n!(n的阶乘)的后缀0的个数

例如：

4!=24 输出0
5!=120 输出1
7!=5040输出1
10!=3628800输出2

//通过这个，简单的先看看阶乘
#include <cstdio>

int main(){

    int n, s = 0, a = 1;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        a = a * i;
        printf("%d!: %d\n", i, a);
    }
    return 0;
}

分析：

　　看有多少个后缀0，则看n！的各个数的素因子中有多少2和5，明显2比5多，所以只需要看5的个数
就ok了

版本一：

//先把除法看成高级一点的减法

看 n! 中有多少个k：sum = n / k;

n ! = 1*2*3*4*5*6*7*8*9*10*11*12*13*14*...*n

5 = 1*5；(素因子中有一个5)
10 = 2*5；
15 = 3*5；
20 = 4*5；
25 = 5*5；（素因子中有两个5）
50 = 2*5*5
125 = 5*5*5 (素因子中有三个5)


//复杂度：O(nlogn) log底数为5
for(int i = 5, sum = 0; i <= n; i += 5){   //n
    int j = i;
    while(j % 5 == 0){                     
        j = j / 5;
        sum++;
    }
}

版本二：

就拿35！来举例吧！
这样来看：
       	         5    10    15    20    25    30    35
素因子中5的个数:  1     1     1     1     2     1     1
除以5后    	 0     0     0     0     1     0     0
//a = 5,先看n！的各个数的素因子中有多少5,然后除5后，把元素中的一个素因子5去掉，
//然后a = a * 5 = 25
25的素因子只有一个5了，除以25，25的素因子5的个数为0。能被25整除的数的素因子中至少
还有一个5，所以25中有一个，30，35中都没有了

//复杂度：O(logn)
a = 1;
sum = 0;
while(1){
    a = a * 5;
    sum = sum + n / a;
    if(a >= n)
        break;
}
printf("%d\n", sum);

版本二改：

//复杂度：O(logn)
s = 0
r = 5;
while(r <= n){
    s += n / r;
    r *= 5;
}

版本三：

s = 0;
while(n /= 5){ //不停的给n除以5，然后把每次相除得来的素因子加起来
    s += n;
}