codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.