Bacteria
Time limit2sMemory limit512 MB
Given n and m up to 1e9, find the shortest sequence of operations (squaring, or dividing by a prime) turning n into m, or report impossible.
- Level
Medium7 of 10
- Topics
- Math, Number theory, Greedy, Implementation
- Solved
- No attempts yet
Problem
Young biologist Anton keeps bacteria in a beautiful glass flask.
By adding various reagents to the flask, Anton can control the number of bacteria. If is a prime number, Anton can prepare at home a substance that, when added to the flask, reduces the number of bacteria by exactly a factor of . If the number of bacteria is not divisible by , the effect of the substance is undefined and the experiment loses its scientific accuracy. Anton does not want this, so he applies the substance only when the number of bacteria is divisible by .
Anton also has an unlimited supply of lysergic acid diethylamide in his kitchen. When lysergic acid diethylamide is added to the flask with bacteria, the number of bacteria is squared.
Anton wants the flask to contain bacteria. He wants to add substances to the flask as few times as possible. Help him do this.
Input
The input file contains two positive integers and (), the initial and desired number of bacteria in Anton's flask.
Output
If it is impossible to obtain exactly bacteria, print the word <<Impossible>> to the output file.
If the desired result is achievable, print the shortest sequence of substance additions that achieves it in the following format: adding substance is encoded by the number , adding substance is encoded by the number 0. The numbers must be separated by spaces and/or newlines.
If there are several shortest sequences of additions leaving bacteria, print any one of them.
Hint
In the first example, Anton needs to add substances to the flask three times: first add \ft{}, halving the number of bacteria, leaving 6 bacteria; then add , squaring the number of bacteria, increasing it to 36; and finally add \ft{} again, dividing the number of bacteria by two and making it equal to 18.