codeforces-scrape

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

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