HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > IMPC - 2013-2014 > problem:


2013-04-80. 50343 - The number of Ending Zeros in n!

IMPC - 2013-2014

Start: Mar.16.2013 at 12:00:00 PM
Finish: Mar.16.2013 at 05:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 2013-03-30. 50559 - Prime Factors ...
• 2013-03-40. 50685 - Guest Room U...
• 2013-04-10. 50335 - Five Math Ope...
• 2013-04-100. 50323 - Filtering Cont...
• 2013-04-30. 50337 - Exam Averages
• 2013-04-40. 50338 - Convert Into ...
• 2013-04-50. 50774 - Hot Potato
• 2013-04-70. 50296 - Total Discount...
• 2013-04-80. 50343 - The numbe...
• 2013-04-90. 50332 - Variance of a ...
• 2013-05-10. 50552 - Casual shoes
• 2013-05-30. 50580 - Days passed
• 2013-05-40. 50553 - Divisible by m
• 2013-05-50. 50593 - Transporter
• 2013-12-10. 50352 - Selling Cows
• 2013-12-40. 50342 - 100 Factorial
• 2013-12-50. 50674 - Collecting Eggs

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Prepared by Ibrahim Mesecan.

The number of Ending Zeros in n!

In Mathematics n! means the product of the numbers 1 through n. That is
   5! = 1x2x3x4x5=120 and it has just 1 ending zeros.
   7!=5040 again has just 1 ending zero.
   10!=3628800 has 2 ending zeros.

In a number, ending zeros can be calculated by counting the number of (2x5) pairs in the factorized form of the number. Hence, 300 has 2 ending zeros; 300 = 3 x (2x5) x (2x5). Because, there will be more 2s than 5s in n!, the number of 5s will give the number of ending zeros.

The number of 5s (and hence the number of ending zeros) can be calculated with this algorithm.
Every number that is divisible by

  • 5 will have at least one 5 in it; like 5, 10, 15, etc.
  • 25 will have at least two 5s in it; like 25, 50, 75, etc.
  • 125 will have at least three 5s in it; like 125, 250, 375, etc.

Question:
Write a program that is going to find out the number of ending zeros in n!

Input specification
You will be given one integer (n) which is 1 ≤ n ≤ 100.000.

Output specification
Give just one number that represent the number of ending zeros in n!

Sample Input I
   1000
Sample Output I
   249
 Sample Input II
   789
 Sample Output II
   195

Output Explanation :
   res =1000 / 5 = 200 ==> there are 200 numbers that have at least one 5,
   res =1000 / 25 = 40 ==> there are 40 numbers that have at least two 5s,
   res =1000 / 125 = 8 ==> there are 8 numbers that have at least three 5s,
   res =1000 / 625 = 1 ==> there is 1 number that has four 5s,
   res =1000 / 3125 = 0 ==> there is 0 number that has five 5s,

The answer is sum of the results 200 + 40 + 8 + 1 = 249

Для отправки решений необходимо выполнить вход.

www.contester.ru