codeforces-scrape

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

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.