2218D.md (1990B)
1 Source: https://codeforces.com/problemset/problem/2218/D 2 3 D. The 67th OEIS Problem 4 5 time limit per test 6 7 2 seconds 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 Macaque, being a terrible problemsetter, decided to search for funny sequences on the OEIS$^{\text{∗}}$ one day, so he could gain inspiration for his doomed problemsetting job for the Pan-Mammalian Olympiad in Informatics (PMOI). To his delight, he found one, and thought it would be funny to make you, his loyal tester, solve it: 22 23 Construct a sequence $a$ containing $n$ integers such that $\operatorname{gcd}(a_i, a_{i+1})$ $^{\text{†}}$ is distinct over all $1 \leq i \leq n - 1$. It is guaranteed that at least one sequence $a$ exists. 24 25 $^{\text{∗}}$Online Encyclopedia of Integer Sequences, the favourite website of math nerds, overly astute testers, and insufficiently rigorous coordinators. 26 27 $^{\text{†}}$$\operatorname{gcd}(x,y)$ refers to the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $x$ and $y$. 28 29 Input 30 31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows. 32 33 The following $t$ lines contain one integer $n$ ($2 \leq n \leq 10^4$) — the desired length of the sequence. 34 35 It is guaranteed the sum of $n$ over all test cases does not exceed $10^4$. 36 37 Output 38 39 For each query, output your answer — a sequence $a$ of $n$ space-separated integers ($1 \le a_i \le 10^{18}$). 40 41 Example 42 43 Input 44 45 ``` 46 2 47 3 48 5 49 ``` 50 51 Output 52 53 ``` 54 1 6 2 55 134 67 69 207 414 56 ``` 57 58 Note 59 60 In the first test case, the sequence $[1, 6, 2]$ is a possible answer. This is because $\gcd(1, 6)$ is not equal to $\gcd(6, 2)$. 61 62 In the second test case, the sequence $[134, 67, 69, 207, 414]$ is a possible answer. This is because the values of $\gcd(a_i, a_{i+1})$ for all $i$ between $1$ and $n-1$ are distinct. For reference, they are $67$, $1$, $69$ and $207$.