DMOPC '16 Contest 2 P4 - Zeros

View as PDF

Submit solution


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

Author:
Problem types

Recall that the factorial function is defined as follows:

\displaystyle N! = N \times (N-1) \times \dots \times 2 \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].

Constraints

Subtask 1 [20%]

0 \le a \le b \le 15

Subtask 2 [30%]

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

Subtask 3 [50%]

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

14

Explanation

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


Comments


  • 5
    thomas0115  commented on Nov. 8, 2016, 10: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


    • -1
      aethiraes  commented on Nov. 9, 2016, 2:47 p.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, 8:16 p.m.

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