Omkar and Last Class of Math
Contest: Codeforces Round 655 (Div. 2)
Difficulty rating: 1300
Tags: greedy, math, number theory

In Omkar's last class of math, he learned about the least common multiple, or $$$LCM$$$. $$$LCM(a, b)$$$ is the smallest positive integer $$$x$$$ which is divisible by both $$$a$$$ and $$$b$$$.

Omkar, having a laudably curious mind, immediately thought of a problem involving the $$$LCM$$$ operation: given an integer $$$n$$$, find positive integers $$$a$$$ and $$$b$$$ such that $$$a + b = n$$$ and $$$LCM(a, b)$$$ is the minimum value possible.

Can you help Omkar solve his ludicrously challenging math problem?

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10$$$). Description of the test cases follows.

Each test case consists of a single integer $$$n$$$ ($$$2 \leq n \leq 10^{9}$$$).

Output format:
For each test case, output two positive integers $$$a$$$ and $$$b$$$, such that $$$a + b = n$$$ and $$$LCM(a, b)$$$ is the minimum possible.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For the first test case, the numbers we can choose are $$$1, 3$$$ or $$$2, 2$$$. $$$LCM(1, 3) = 3$$$ and $$$LCM(2, 2) = 2$$$, so we output $$$2 \ 2$$$.

For the second test case, the numbers we can choose are $$$1, 5$$$, $$$2, 4$$$, or $$$3, 3$$$. $$$LCM(1, 5) = 5$$$, $$$LCM(2, 4) = 4$$$, and $$$LCM(3, 3) = 3$$$, so we output $$$3 \ 3$$$.

For the third test case, $$$LCM(3, 6) = 6$$$. It can be shown that there are no other pairs of numbers which sum to $$$9$$$ that have a lower $$$LCM$$$.

Example input:
3
4
6
9

Example output:
2 2
3 3
3 6

Editorial:
Short Solution: The two integers are $$$k$$$ and $$$n-k$$$, where $$$k$$$ is the largest proper factor of $$$n$$$.
Proof: Let the two integers be $$$k$$$ and $$$n-k$$$. Assume WLOG that $$$k \leq n-k$$$. Notice that this implies that $$$n - k \geq \frac n 2$$$.
We first claim that $$$LCM(k, n-k) = n-k < n$$$ if $$$k \mid n$$$, and we prove this as follows: if $$$k \mid n$$$, then there exists some integer $$$m$$$ such that $$$m \cdot k = n$$$. The integer $$$n-k$$$ can then be written as $$$(m-1) \cdot k$$$, which is a multiple of $$$k$$$. Thus, $$$LCM(k, n-k) = n-k $$$ if $$$k \mid n$$$.
We now show that $$$LCM(k, n-k) \geq n$$$ if $$$k \nmid n$$$. We show this by using the fact that $$$LCM(a, b) = b$$$ iff $$$a \mid b$$$, so if $$$k \nmid n$$$, $$$k \nmid n - k$$$, and so $$$LCM(k, n-k) \neq n-k$$$. And since $$$LCM(k, n - k)$$$ must be a multiple of both $$$k$$$ and $$$n - k$$$, it follows that $$$LCM(k, n-k) \geq 2 \cdot (n-k) \geq 2 \cdot \frac n 2 = n$$$.
We have now established that to minimize $$$LCM(k, n-k)$$$, $$$k$$$ must be a factor of $$$n$$$. And, since $$$LCM(k, n-k) = n-k$$$ when $$$k$$$ is a factor of $$$n$$$, we need to minimize $$$n-k$$$, so we must maximize $$$k$$$ by choosing it to be the largest proper factor of $$$n$$$ (i. e. the largest factor of $$$n$$$ other than $$$n$$$).
We then simply need to find $$$k$$$, the largest proper factor of $$$n$$$. If $$$p$$$ is the smallest prime dividing $$$n$$$, then $$$k = \frac n p$$$, so it suffices to find the smallest prime factor of $$$n$$$. We can do this by simply checking all values of $$$p$$$ such that $$$2 \leq p \leq \sqrt n$$$. If $$$n$$$ is not prime, then it must have a prime factor not exceeding $$$\sqrt{n}$$$. Furthermore, if we do not find a factor of $$$n$$$ between $$$2$$$ and $$$\sqrt n$$$, then $$$n$$$ must be prime so we simply get $$$p = n$$$ and $$$k = \frac n p = 1$$$.
We're given that $$$n \leq 10^9$$$, so $$$\sqrt n \leq 10^{\frac 9 2} < 10^5$$$. $$$t \leq 10$$$, meaning that we will check less than $$$10^6$$$ numbers, which runs well under the time limit.