Problem F
Product Digit
Languages
en
sv
Nikolaj works at a company that sells a large number of products. Each product has a product ID, which is a large integer. For error detection, in particular in connection with manual database entry, it would be useful if each product also had a single “check” digit between $1$ and $9$ that can be quickly computed from the product ID. Nikolaj has been tasked with implementing this. He recently solved the problem “Digit Product” on Open Kattis and considers using the procedure described there.
He recalls that the idea is to start with a positive integer $x$ and repeatedly multiply all its nonzero digits, until only a single digit is left. For instance, if $x$ is $808$ then the resulting digit is $8$, because $8 \cdot 8 = 64$, $6 \cdot 4 = 24$, and $2 \cdot 4 = 8$.
However, Nikolaj is unsure about using this method, because the distribution of resulting digits seems uneven to him. To determine how the distribution looks, he writes a program that given two integers $L$ and $R$ determines how many numbers in the interval $[L, R]$ result in each digit.
Input
A single line consisting of two integers $L$ and $R$ with $1 \leq L \leq R \leq 10^{15}$.
Output
Print $9$ integers $a_1, a_2, \ldots , a_9$ on a single line. The $i$th number $a_ i$ is the number of integers $x$ satisfying $L \leq x \leq R$ such that repeated multiplication of the nonzero digits of $x$ results in the digit $i$.
| Sample Input 1 | Sample Output 1 |
|---|---|
50 100 |
3 7 4 6 5 7 2 15 2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 7 |
0 0 1 1 1 1 1 0 0 |
