# B. Add 0 or K [문제 링크](https://codeforces.com/contest/2134/problem/B) ## Problem Statement You are given an array of $n$ positive integers $a_1,a_2,\ldots,a_n$ and a positive integer $k$. 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 \leftarrow a_i + b_i$ for $ 1 \le i \le n$ Note that you can choose different values for each element of the array $b$. Your task is to perform at most $k$ such operations to make $\gcd(a_1,a_2,\ldots,a_n) > 1$. It can be proved that this is always possible. Output the final array after the operations. You do **not** have to output the operations themselves. ## Input Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 10^5$, $1 \le k \le 10^9$) — the length of the array $a$ and the given constant. 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$. It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. ## Output For each test case, output an array of $n$ integers in a new line — the final array after the operations. If there are multiple valid outputs, you can output any of them. Note that you do **not** have to minimize the number of operations. ## Footnotes $^{\text{∗}}$\gcd(a_1, a_2, \ldots, a_n)$ denotes the <a href="https://en.wikipedia.org/wiki/Greatest_common_divisor">greatest common divisor (GCD)</a> of $a_1, a_2, \ldots, a_n$. ## 풀이 #### k가 홀수인 경우, 홀짝성을 이용해 1번만 더해 홀수나 짝수로 만들 수 있다. #### k가 짝수인 경우, a[i]를 k+1로 나눈 나머지가 m인 경우, m을 k번 더해서 나머지를 0으로 만들 수 있다는 아이디어를 사용하여 구현한다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { ll n, k; cin >> n >> k; vector<ll> a(n); for(int i=0;i<n;i++) cin >> a[i]; if(k%2==1) { for(int i=0;i<n;i++) { if(a[i]%2==0) cout << a[i] << ' '; else cout << a[i]+k << ' '; } } else { for(int i=0;i<n;i++) cout << a[i]+(a[i]%(k+1))*k << ' '; } cout << '\n'; } } ```