1024: 末位零
Time Limit: 1 Sec Memory Limit: 32 MB
Submit: 60 Solved: 11
[Submit][Status][Web
Board]
Description
给定一个正整数N，那么N的阶乘N！末尾有多少个0呢？例如：N＝10，N！＝3 628 800，N！的末尾有两个0。
注意：N<=100,000,000
Input
第一行为N，表示有N个输入。接下来有N行，每一行包括一个正整数。
Output
对于每个输入，每行输出结果
Sample Input
2
5
10
Sample Output
1
2
求N的阶乘的末尾几个0，刚开始只知道出现2与5就会有0，后来百度一下发现只要是5的倍数均会+1，贴上原帖思路：
把从 1000 到 1 这些所有的数，只要是5的倍数的，一律分解成含因子5为止。
例如
10 = 2 * 5
15 = 3 * 5
25 = 5 * 5
50 = 2 * 25 = 2 * 5 * 5
100 = 4 * 25 = 4 * 5 * 5
105 = 21 * 5
125 = 5 * 5 * 5 余此类推。
从1 到1000，能被5 整除的数有 1000/5 = 200 个 能被5的平方即25整除的数有 1000/25 = 40 个 能被5的立方即125整除的数有 1000/125 = 8 个
能被5的4次方即625 整除的数有 1000/625 = 1个 （即625自己）
把这1000个数，只要能分解出因子5，就一直分解到因子5为止。共可分解出 200 + 40 + 8 + 1 = 249 即最终可分解出 249 个5。
只要有1个5，与偶数相乘后就会出现1个0。 而 从1 到1000，偶数的数量是足够的，所以 有249个5，乘积结果中就有249个0。
由于数据比较大到10^8用longlong，又可以用到可爱的快速幂了，13次方显然没卵用- -|||.
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<set>
#include<map>
#include<sstream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
inline long long POW5(int b)
{
long long r=1,bas=5;
while (b!=0)//蛋疼b写成rWA了一次
{
if(b&1)
r*=bas;
bas*=bas;
b>>=1;
}
return r;
}
int main (void)
{
long long n,temp;
int t;
scanf("%d",&t);
while (t--)
{
scanf("%lld",&n);
long long ans=0;
for (int i=1; i<13; i++)//5的13次我用计算器算了一下大于10^8次了，直接到这够了
{
temp=POW5(i);//调试方便查看
ans=ans+n/temp;
}
cout<<ans<<endl;
}
return 0;
}