Virat loves mathematical questions. The other day he came across an interesting question which required him to find out the number of trailing zeroes for the
function.?F(n) = 11*22......NN,where?N?is an integer. Virat solved the problem after a few attempts. He asked the same
question from his friend Rohit to see if he can solve it. Rohit couldn’t arrive at a solution and has asked for your help. Can you help him out?
Input
- The first line contains a single integer?T,the number of test cases.?T?test cases follow.
- Each line contains a single integer
N.
Output
For each test case,output a single line containing a single integer which denotes the number of trailing zeroes for the value of the function computed for
N.
Constraints
-
1?<=?T?<=?1000
-
1?<=?N?<=?10000
Example
Input:
3
5
10
2
Output:
5
15
0
http://www.codechef.com/problems/ZEROES
F(n) = 11*22......NN,求F(n)的末位有几个0。这种题目就是要找规律。因为值实在是太大了,只能算出前几个,于是我就用了字符串大数模板,也只能勉强算出前200个,规律找得不够彻底。。。
0000 55555 1515151515(为方便我把5个数缩成1个)30 50 100 130 165 205 250 350 405 465 530 600 750 830 915 1005 1100 1300 1405 1515 1630 1750 2125....
我们知道 0 1 3 6 10 15....这个数列的前n项和为 n*(n+1)/2 ,上面白色背景的数字就是它的5倍,间隔为5(前面省去一样的了),红色部分减去白色的值是它的25倍,间隔为25,绿色部分减去红色的值是它的125倍,间隔为125,后面以此类推。
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
#include<cmath>
#include<string.h>
#include<stdlib.h>
#include<cstdio>
#define ll long long
using namespace std;
int main(void){
int t;
scanf("%d",&t);
while(t--){
int n;
cin>>n;
ll s=0;
for(int i=1;pow(5.0,i)<=n;++i){
int m=n/pow(5.0,i);
s+=pow(5.0,i)*(m+1)*m/2;
}
printf("%I64dn",s);
}
return 0;
}
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
#include<cmath>
#include<string.h>
#include<stdlib.h>
#include<cstdio>
#define ll long long
using namespace std;
int main (void)
{
int t;
scanf("%d",&t);
while(t--)
{
int n,i;
long long int zero=0;
scanf("%d",&n);
for(i=5;i<=n;i+=5)
{
if(i%78125 == 0)
zero += i*7;
else if(i%12625 == 0)
zero += i*6;
else if(i%3125 == 0)
zero += i*5;
else if(i%625 == 0)
zero += i*4;
else if(i%125 == 0)
zero += i*3;
else if(i%25 == 0)
zero += i*2;
else
zero += i;
}
printf("%lldn",zero);
}
}