2267C.md (2330B)
1 Source: https://codeforces.com/problemset/problem/2267/C 2 3 C. GCD Treasury 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 The greedy pirate Dimash found a treasury. It consists of $n$ piles of coins, numbered from $1$ to $n$. The $i$-th pile contains exactly $a_i$ coins. Pirate Dimash has a number $x$ that he can use to steal coins from the treasury. The stealing process works as follows: 22 23 * First, he chooses an index $1\le i\le n$ such that $a_i\gt 0$ and $\gcd$$^{\text{∗}}$$(a_i, x) \neq 1$. If there is no such index, the pirate stops. 24 * Now let $\gcd(a_i, x)$ be $g$. The pirate steals exactly $g$ coins from pile $i$, after which $a_i$ decreases by $g$. 25 * Finally, he sets $x$ to $g$ and continues stealing coins. 26 27 Your task is to help the pirate steal the maximum possible number of coins. Find the maximum number of coins that can be stolen from the treasury. 28 29 $^{\text{∗}}$$\gcd(a_i, x)$ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $a_i$ and $x$. 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 10^4$). The description of the test cases follows. 34 35 The first line of each test case contains two integers $n$ and $x$ ($1\le n, x\le 3\cdot 10^5$) — the number of piles of coins in the treasury and the pirate's number. 36 37 The second line of each test case contains $n$ integers $a_1, a_2, \ldots a_n$ ($1 \le a_i \le 3\cdot 10^5$). 38 39 It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot 10^5$. 40 41 Output 42 43 For each test case, output one number — the maximum number of coins that can be stolen. 44 45 Example 46 47 Input 48 49 ``` 50 5 51 52 3 1 53 54 2 3 5 55 56 3 4 57 58 2 3 4 59 60 4 2 61 62 2 2 2 2 63 64 6 6 65 66 2 3 2 3 2 3 67 68 7 6 69 70 9 9 4 4 4 4 4 71 ``` 72 73 Output 74 75 ``` 76 0 77 78 6 79 80 8 81 82 9 83 84 20 85 ``` 86 87 Note 88 89 In the first test case, no coin can be stolen. 90 91 In the second test case, the pirate steals as follows. 92 93 * The pirate chooses pile number $3$. He takes $4$ coins, after which the treasury becomes $[2, 3, 0]$ and $x$ becomes $4$. 94 * The pirate chooses pile number $1$. He takes $2$ coins, after which the treasury becomes $[0, 3, 0]$, and $x$ becomes $2$. 95 * No suitable indices remain, so the pirate stops. The pirate managed to take $4 + 2 = 6$ coins.