1372B.md (1555B)
1 Source: https://codeforces.com/problemset/problem/1372/B 2 3 B. Omkar and Last Class of Math 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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$. 22 23 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. 24 25 Can you help Omkar solve his ludicrously challenging math problem? 26 27 Input 28 29 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. 30 31 Each test case consists of a single integer $n$ ($2 \leq n \leq 10^{9}$). 32 33 Output 34 35 For each test case, output two positive integers $a$ and $b$, such that $a + b = n$ and $LCM(a, b)$ is the minimum possible. 36 37 Example 38 39 Input 40 41 ``` 42 3 43 4 44 6 45 9 46 ``` 47 48 Output 49 50 ``` 51 2 2 52 3 3 53 3 6 54 ``` 55 56 Note 57 58 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$. 59 60 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$. 61 62 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$.