[Solution] Number Transformation solution codeforces

Number Transformation solution codeforces – You are given two integers 𝑥x and 𝑦y. You want to choose two strictly positive (greater than zero) integers 𝑎a and 𝑏b, and then apply the following operation to 𝑥x exactly 𝑎a times: replace 𝑥x with 𝑏𝑥b⋅x.

[Solution] Number Transformation solution codeforces

You want to find two positive integers 𝑎a and 𝑏b such that 𝑥x becomes equal to 𝑦y after this process. If there are multiple possible pairs, you can choose any of them. If there is no such pair, report it.

For example:

  • if 𝑥=3x=3 and 𝑦=75y=75, you may choose 𝑎=2a=2 and 𝑏=5b=5, so that 𝑥x becomes equal to 355=753⋅5⋅5=75;
  • if 𝑥=100x=100 and 𝑦=100y=100, you may choose 𝑎=3a=3 and 𝑏=1b=1, so that 𝑥x becomes equal to 100111=100100⋅1⋅1⋅1=100;
  • if 𝑥=42x=42 and 𝑦=13y=13, there is no answer since you cannot decrease 𝑥x with the given operations.
Input

The first line contains one integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases.

Each test case consists of one line containing two integers 𝑥x and 𝑦y (1𝑥,𝑦1001≤x,y≤100).

[Solution] Number Transformation solution codeforces

If it is possible to choose a pair of positive integers 𝑎a and 𝑏b so that 𝑥x becomes 𝑦y after the aforementioned process, print these two integers. The integers you print should be not less than 11 and not greater than 109109 (it can be shown that if the answer exists, there is a pair of integers 𝑎a and 𝑏b meeting these constraints). If there are multiple such pairs, print any of them.

If it is impossible to choose a pair of integers 𝑎a and 𝑏b so that 𝑥x becomes 𝑦y, print the integer 00 twice.

Example
input

Copy
3
3 75
100 100
42 13

Number Transformation solution codeforces

output

Copy
2 5
3 1
0 0

 

For Solution

Click here

Leave a Comment