P2406 Minimum Sum

The RSA algorithm is based on a very simple number-theoretic fact: multiplying two large primes is easy, but factoring their product is extremely difficult. Therefore, the product can be published as an encryption key. As a result, only short RSA keys can be cracked by brute force today.

Given that $a, b$ are positive integers with $a \leq b$. Find $x, y$ that satisfy the conditions and minimize $x + y$. Conditions: - $\gcd(x, y) = a$; - $\mathrm{lcm}(x, y) = b$; - $x \leq y$.

Multiple test cases, terminated by EOF. There are at most $10^3$ lines, each containing two numbers $a, b$.

Output the same number of lines as in the input. For each line, output two numbers $x, y$, separated by a single space.

$3 \leq a, b < 2^{63}$. Terminated by EOF; there is no line count $n$, and the first line is testdata. The testdata are randomly generated. Translated by ChatGPT 5