Here is the problem statement
http://www.spoj.com/problems/FCTRL/
N!=1*2*3*4*...*N
If we factorize N we can be sure that there are more factors 2 than factors 5*5=10 (ends in 0 ) so in other words we need to find the number of factors 5 in N!. The obvious approach is looping over number from 1 to N and every time we meet a number which is divisible on 5 we calculate the number of 5 factors and add them to our answer. Unfortunately it won't pass the time limit.
Let's have a look at a few numbers.
N=27;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
I suggest that the amount of numbers divisible on 5 is N/5 ( / means divided without taking the remainder) 27/5=5 and which is true.
I suggest that the amount of numbers divisible on 25 is N/25. 27/25=1 and which is also true. So our final formula will look like this
ans= ans+ N divided to all powers of 5 which are less than N)
http://www.spoj.com/problems/FCTRL/
N!=1*2*3*4*...*N
If we factorize N we can be sure that there are more factors 2 than factors 5*5=10 (ends in 0 ) so in other words we need to find the number of factors 5 in N!. The obvious approach is looping over number from 1 to N and every time we meet a number which is divisible on 5 we calculate the number of 5 factors and add them to our answer. Unfortunately it won't pass the time limit.
Let's have a look at a few numbers.
N=27;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
I suggest that the amount of numbers divisible on 5 is N/5 ( / means divided without taking the remainder) 27/5=5 and which is true.
I suggest that the amount of numbers divisible on 25 is N/25. 27/25=1 and which is also true. So our final formula will look like this
ans= ans+ N divided to all powers of 5 which are less than N)
No comments:
Post a Comment