F004B. Stable products P89407

Statement

html

The product of x by y is stable if the digits of x and y on one hand, and the digits of x * y on the other hand, are the same ones.

For instance, the product

 875 * 650 = 568750

is stable because in the both sides there is a 0, two 5, a 6, a 7 and a 8.

This property can be extended to other bases different of 10. For instance, the product of 3 by 53 is stable in base 2:

 11 * 110101 = 10011111

because in both sides there are two 0 and six 1.

Your task is to write a program that, given a sequence of pairs x and y, prints which bases between 2 and 16 (both included) the product x * y is stable for.

To solve this problem, you must implement and use the function

that indicates if, in base b (2≤ b≤ 16), x and y in one hand, and x * y in the other one, have the same digits.

You must implement and use also the procedure

that prints n in base b in the screen (just like that, without spaces nor line feeds).

Input

The input is a sequence of pairs of natural numbers x and y. x ≥ 1, y ≥ 1, x * and ≤ 109 are fulfilled. You can assume this information as a precondition of your procedures.

Output

For each pair x and y, print which bases the product x * y is stable for. If there is not any base, print it. It must print a line feed after the output of each case. Follow the format of the instance.

Observation

If you do tests with random numbers and your program do not find any solution, do not worry: most products are not stable.

Public test cases
• Input

```875 650
3 53
140 245
1 1
118 224
```

Output

```solutions for 875 and 650
1101101011 * 1010001010 = 10001010110110101110 (base 2)
31223 * 22022 = 2022312232 (base 4)
4015 * 3002 = 20105034 (base 6)
875 * 650 = 568750 (base 10)

solutions for 3 and 53
11 * 110101 = 10011111 (base 2)

solutions for 140 and 245
10001100 * 11110101 = 1000010111111100 (base 2)
2030 * 3311 = 20113330 (base 4)
8C * F5 = 85FC (base 16)

solutions for 1 and 1
none of them

solutions for 118 and 224
A8 * 194 = 1894A (base 11)

```
• Information
Author
Professorat de P1
Language
English
Translator
Carlos Molina
Original language
Catalan
Other languages
Catalan
Official solutions
C++
User solutions
C++