COI '07 #4 Umnozak

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 0.6s
Memory limit: 32M

Problem type

The digit-product of a positive integer is the product of the number's decimal digits. For example, the digit-product of 2612 is 2 \cdot 6 \cdot 1 \cdot 2 = 24.

The self-product of a number is the product of the number and its digit-product. For example, the self-product of 2612 is 2612 \cdot 24 = 62\,688.

Write a program that, given two positive integers A and B, calculates the number of positive integers whose self-product is between A and B, inclusive.

Input Specification

The first and only line contains two integers A and B (1 \le A \le B < 10^{18}).

Output Specification

Output should consist of a single integer, the number of positive integers whose self-product is between A and B.

Scoring

In test cases worth a total of 25 points, A and B will be at most 10^8.

In test cases worth another 15, A and B will be at most 10^{12}.

Sample Input 1

20 30

Sample Output 1

2

Sample Input 2

145 192

Sample Output 2

4

Clarification of second example. The self-products of numbers 19, 24, 32 and 41 are in order 171, 192, 192 and 164.

Sample Input 3

2224222 2224222

Sample Output 3

1

Comments

There are no comments at the moment.