1073: 阶乘

题目描述

给一个整数，请输出该数字阶乘的后缀0的个数，例如：
数字7，它的阶乘为5040，后面有一个0，则输出1；还有数字10，它的阶乘为3628800，后面有两个0，则输出2。

输入

第一行一个数据N，小于100，表示一共要输入n个数字，以后n行输入一个数字。

输出

对应于每一个输入，输出一个满足题目要求的数字。

样例输入

6
3
60
100
1024
23456
8735373

样例输出

0
14
24
253
5861
2183837

思路

不会有人要算出阶乘然后判断吧, 我开始写了一个计算阶乘, 还用了字符串存数字, 模拟手算. 然后发现自己是一个蠢蛋. 试问8735373的阶乘是多少捏.

正确思路是因式分解, 2和5可以凑出一个0. 因为是乘法, 0 不会变成其他数字, 因此0会越积越多.

这里举一个例子:

10! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10
分解因式
10! = (1*1) * (1*2) * (1*3) * (2*2) * (1*5) * (2*3) * (1*7) * (2*2*2) * (3*3) * (2*5)
从这个式子中可以提出 2*5*2*5*2*2*2*2*2*2, 里面有两个2*5, 因此10!末尾有2两个0

通过上面的计算过程不难得出, 只需要找到5即可, 有几个5最终就有几个0 (2的数量永远大于等于5的数量, 不服自己推, 我做对了说话就是硬气)

因此可以这样, 以60!举例

60/5 = 12 # 60以内因子只有一个5的个数
12/5 = 2 # 60以内因子只有两个5的个数
2/5 = 0 结束计算 # 60以内因子只有3个5的个数
12+2 = 14
60!末尾有14个0

代码

#include<stdio.h>
int main(){
    int n = 0;
    scanf("%d",&n);
    while(n--){
        int c, s = 0;
        scanf("%d",&c);
        while(c/5 != 0){
            s += c/5;
            c /= 5;
        }
        printf("%d\n",s);
    }
    return 0;
}