NEFU118 n!后面有多少个零【算术基本定理】
题目链接：
http://acm.nefu.edu.cn/JudgeOnline/problemshow.php?problem_id=118
题目大意：
问：计算N！末尾0的个数。(1 <= N <= 1000000000)。
思路：
N是100000000规模的数，直接计算结果，再统计0的个数显然不科学。将末尾0分解为2*5。
每一个0必然和一个因子5对应，但是一个数的因式分解中一个因子5不一定对应一个0。因为
还需要一个因子2，才能实现一一对应。
对于N!，在因式分解中，因子2的个数明显大于因子5的个数。所以如果存在一个因子5，那么
必然对应着N!末尾的一个0。这道题就变为了求N!中因子5的个数。由算术基本定理的性质(5)
可知：N!在素因子分解中素数p的幂为[N/p] + [N/p^2] + [N/p^3] + …，可以直接循环计算。
此时，5的幂就是N!中因子5的个数，也就是N!末尾0的个数。
附算术基本定理的定义和性质：
定理：
每个大于1的正整数N都可以被唯一地写成素数的乘积，在乘积中的素因子按照非降序排列。
正整数N的分解式 N = p1^α1 * p2^α2 * p3^α3 * … * pk^αk 称为N的标准分解式，其中
p1，p2，…，pk是素数，p1 < p2 < p3 < … < pk，且α1，α2，α3，…，αk是正整数。
性质：
(1)若N的标准素因子分解表达式为：N = p1^α1 * p2^α2 * p3^α3 * … * pk^αk，设d(N)
为N的挣银子个数， Φ(N)为N的所有因子之和，则有
d(N) = (α1 + 1) * (α2 + 1) * (α3 + 1) * … * (αk + 1)
Φ(N) = ( p1^(α1 + 1) )/(p1 - 1) * ( p2^(α2 + 1) )/(p2 - 1) * … * ( pk^(αk + 1) )/(pk - 1)
(2)设a = p1^α1 * p2^α2 * … * pk^αk，b = p1^ β1 * p2^β2 * … * pk^βk，则有
gcd(a，b) = p1^min(α1，β1) * p2^min(α2，β2) * … * pk^min(αk，βk)
lcm(a，b) = p1^max(α1，β1) * p2^max(α2，β2) * … * pk^max(αk，βk)
(3)如果a和b为实数，则
max( gcd(a，b) ) + min( gcd(a，b) ) = a + b
(4)如果a和b是正整数，则
lcm(a，b) = a*b/gcd(a，b)
(5)N!的素因子分解中的素数p的幂为
[N/p] + [N/p^2] + [N/p^3] + …
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
int T,N;
cin >> T;
while(T--)
{
cin >> N;
int t,five,sum;
t = N;
five = 5;
sum = 0;
while(five <= t)
{
sum = sum + t/five;
five *= 5;
}
cout << sum << endl;
}
return 0;
}