PROBLEM LINK
Practice http://www.codechef.com/INLO2015/problems/ZEROES
Contest http://www.codechef.com/INLO2015
Editorialist: Ravit Singh Malik http://www.codechef.com/users/ravit007
DIFFICULTY:
easy
PREREQUISITES:
Maths
PROBLEM
You are required to find the number of trailing zeroes of F(n) = 1^12^23^3*…*N^N,
QUICK EXPLANATION
suppose uou have to find the number of zeroes in a product. 24*32*23*19=( 2^3*3^1)*2^5*23*19 as you can notice, this product will have no zeroes because it has no 5 in it.however, if you have expression like: 81523172522
it is equal to 2^33^15^123175^22^111^1
Zeroes are formed by the cobination of 2*5. Hence,the number of zeroes will depend on number of pairs
of 2’s and 5’s that can be formed.
In the above product, there are four twos and three fives.Hence, ther will be 3 Zeroes in the product.
EXPLANATION:
In the given problem You are required to find the number of trailing zeroes of F(n) = 1^12^23^3*…*N^N,
so, if n=32
F(n) = 1^12^23^3*…32^32,
so,the fives will be less than twos. Hence, we need to count only the fives.
Thus: 5^510^1015^1520^2025^2530^30
give us: 5+10+15+20+25+25+30
we take 25 two times because it have two fives each.
thus the f(n) has 130 trailing zeroes.
Pseudocode:
Start
input test cases t
while(t–)
input n
begin of loop
for(a=5,b=0;a<=n;a+=5)
l=1;
k=a/5;
while(k%5==0)
{
k=k/5;
l++;
}
b=b+a*l;
end of loop
print b
end
end