Hide

Problem A
Same Digits (Hard)

/problems/samedigitshard/file/statement/en/img-0001.jpg
Image by Andrey Druc (Shutterstock); Used under license

Two positive integers, $x$ and $y$, are called digit-preserving if their product, $xy$, contains exactly the same digits as $x$ and $y$ contain together, including repetitions. For example, if $x = 807$ and $y = 984$, then their product, $794088$, contains $\textrm{one}~ 7$, $\textrm{one}~ 9$, $\textrm{one}~ 4$, $\textrm{one}~ 0$, and $\textrm{two}~ 8\textrm{'s}$, which is exactly the same set of digits and corresponding frequencies as in $807$ and $984$ combined.

Given an interval, $[A,B]$, find all digit-preserving pairs, $x, y$, in the interval, with the additional requirement that their product must also be in the same interval, i.e., all three of $x, y, xy$ are in $[A,B]$. To avoid double-counting, you can assume $x \leq y$ (this avoids, for example, treating $(807, 984)$ and $(984, 807)$ as different digit-preserving pairs).

Input

The input consists of a single line containing two space-separated integers, $A$ and $B$, with $1 \leq A \leq B \leq 200\, 000$.

Output

First output a single line containing “$n$ digit-preserving pair(s)”, where $n$ is the number of digit-preserving pairs in $[A,B]$ (as described above). Then output $n$ lines, each of which contains one of the digit-preserving pairs and the corresponding product. Carefully format your output as in the sample output (note the single space separating adjacent tokens). These lines should be sorted by increasing value $\textrm{of}~ x$, breaking ties by increasing value $\textrm{of}~ y$.

Sample Input 1 Sample Output 1
1 1000
3 digit-preserving pair(s)
x = 3, y = 51, xy = 153
x = 6, y = 21, xy = 126
x = 8, y = 86, xy = 688
Sample Input 2 Sample Output 2
1000 2000
0 digit-preserving pair(s)

Please log in to submit a solution to this problem

Log in