EGOI '21 P1 - Zeros

View as PDF

Submit solution

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

Problem type
European Girls' Olympiad in Informatics: 2021 Day 1 Problem 1

Santa Claus is already preparing for Christmas 2021. He wants to buy some positive number of presents, such that he will be able to divide them evenly (without remainder) among all eligible (not naughty) children. However, he does not yet know how many eligible children there will be - he only knows that this number will be between a and b. Therefore, he wants to buy the minimum positive number of presents that can be divided evenly between any number x of children with x \in \{a, a+1, \dots, b\}.

He has computed this (possibly huge) number of presents, but he is unsure about the correctness, and he would like your help in performing the following basic sanity check. Are you able to tell him how many zero digits there should be at the end of this number?

Input Specification

The first and only line of the input consists of two space-separated integers a and b (1 \le a \le b \le 10^{18}).

Output Specification

Output a single integer — the number of zeros at the end of the number of presents that Santa needs to buy.

Constraints

Subtask Points Constraints
1 6 b \le 16
2 7 b \le 40
3 9 a = 1 and b \le 200
4 12 b-a \le 10^6
5 17 a = 1
6 49 No additional constraints.

Sample Input 1

1 6

Sample Output 1

1

Explanation for Sample Output 1

If there can be between 1 and 6 children, then Santa needs at least 60 presents (as this is the smallest number that is divisible by all of 1, 2, 3, 4, 5 and 6), and the number 60 has a single zero at the end.

Sample Input 2

10 11

Sample Output 2

1

Explanation for Sample Output 2

If there can be either 10 or 11 children, Santa will buy 110 presents.


Comments

There are no comments at the moment.