F004B. Stable products P89407


Statement
 

pdf   zip

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++