codeforces-scrape

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

2134B.md (2912B)


      1 Source: https://codeforces.com/problemset/problem/2134/B
      2 
      3 B. Add 0 or K
      4 
      5 time limit per test
      6 
      7 1.5 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 You are given an array of $n$ positive integers $a_1, a_2, \ldots, a_n$ and a positive integer $k$.
     22 
     23 In one operation, you may add either $0$ or $k$ to each $a_i$, i.e., choose another array of $n$ integers $b_1, b_2, \ldots, b_n$ where each $b_i$ is either $0$ or $k$, and update $a_i$ to $a_i + b_i$ for $1 \le i \le n$. Note that you can choose different values for each element of the array $b$.
     24 
     25 Your task is to perform at most $k$ such operations to make $\gcd(a_1, a_2, \ldots, a_n) \gt 1$ $^{\text{∗}}$. It can be proved that this is always possible.
     26 
     27 Output the final array after the operations. You do not have to output the operations themselves.
     28 
     29 $^{\text{∗}}$$\gcd(a_1, a_2, \ldots, a_n)$ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of $a_1, a_2, \ldots, a_n$.
     30 
     31 Input
     32 
     33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.
     34 
     35 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 10^5$, $1 \leq k \leq 10^9$) — the length of the array $a$ and the given constant.
     36 
     37 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$) — the elements of the array $a$.
     38 
     39 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     40 
     41 Output
     42 
     43 For each test case, output an array of $n$ integers in a new line — the final array after the operations. The integers in the output should be within the range from $1$ to $10^9 + k^2$.
     44 
     45 If there are multiple valid outputs, you can output any of them.
     46 
     47 Note that you do not have to minimize the number of operations.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 8
     55 
     56 3 3
     57 
     58 2 7 1
     59 
     60 4 5
     61 
     62 2 9 16 14
     63 
     64 4 1
     65 
     66 1 2 3 4
     67 
     68 5 2
     69 
     70 5 6 7 8 9
     71 
     72 2 10
     73 
     74 7 9
     75 
     76 1 1000000000
     77 
     78 1
     79 
     80 1 371
     81 
     82 1000000000
     83 
     84 3 6
     85 
     86 1 3 5
     87 ```
     88 
     89 Output
     90 
     91 ```
     92 8 10 10
     93 7 14 21 14
     94 2 2 4 4
     95 9 6 9 12 9
     96 77 99
     97 1000000000000000001
     98 1000000000
     99 25 15 5
    100 ```
    101 
    102 Note
    103 
    104 In the first test case, the output $[8,10,10]$ is valid because $\gcd(8, 10, 10) = 2 \gt 1$, and the array $[2, 7, 1]$ can be transformed into $[8, 10, 10]$ using at most $3$ operations. One possible sequence of operations is shown below:
    105 
    106 |  |  |  |
    107 | --- | --- | --- |
    108 | Operation | $b$ | Resulting $a$ |
    109 | $1$ | $[3,0,3]$ | $[5,7,4]$ |
    110 | $2$ | $[0,0,3]$ | $[5,7,7]$ |
    111 | $3$ | $[3,3,3]$ | $[8,10,10]$ |
    112 
    113 Other outputs like $[2, 10, 4]$, $[8, 16, 4]$, and $[5, 10, 10]$ are also considered valid.
    114 
    115 In the second test case, the output $[7, 14, 21, 14]$ is valid because:
    116 
    117 * $\gcd(7, 14, 21, 14) = 7 \gt 1$.
    118 * Starting from $[2, 9, 16, 14]$, applying the operation with $b = [5, 5, 5, 0]$ yields $[7, 14, 21, 14]$, requiring no more than $5$ operations.