DMOPC '16 Contest 2 P4 - Zeros

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Recall that the factorial function is defined as follows:

\displaystyle N!=N \times (N-1) \times (N-2) \times \dots \times 1

Given integers a and b, please find the number of natural numbers N such that N! has a number of trailing zeros in the range of [a, b].


Subtask 1 [20%]

0 \le a \le b \le 15

Subtask 2 [30%]

0 \le a \le b \le 10^5

For the remaining 50% of the testcases, 0 \le a \le b \le 10^9.

Input Specification

The first line of the input contains the two integers a and b.

Output Specification

The number of values of N that satisfy the condition.

Sample Input

0 2

Sample Output



1! = 1 is the first element that satisfies the condition, and 14! = 87\,178\,291\,200 is the last element. Hence, there are a total of 14 values of N that satisfies the condition.


  • 4
    thomas0115  commented on Nov. 8, 2016, 5:47 p.m. edited

    In the explanation you imply that natural numbers are 1,2,3, etc. but in the input specification you say a,b>=0

    • 0
      aethiraes  commented on Nov. 9, 2016, 9:47 a.m. edited

      Natural numbers of set N can be 0,1,2,3... or 1,2,3...

      Wikipedia says there's no agreement on which one is "standard", whether 0 is included or not.

      The set N* is used to specify positive numbers only, 1,2,3,4...

      • 5
        r3mark  commented on Nov. 9, 2016, 3:16 p.m.

        Yes, but this problem's usage of natural numbers isn't consistent which led to confusion.