codeforces-scrape

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

1883C.md (2028B)


      1 Source: https://codeforces.com/problemset/problem/1883/C
      2 
      3 C. Raspberries
      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 You are given an array of integers $a_1, a_2, \ldots, a_n$ and a number $k$ ($2 \leq k \leq 5$). In one operation, you can do the following:
     22 
     23 * Choose an index $1 \leq i \leq n$,
     24 * Set $a_i = a_i + 1$.
     25 
     26 Find the minimum number of operations needed to make the product of all the numbers in the array $a_1 \cdot a_2 \cdot \ldots \cdot a_n$ divisible by $k$.
     27 
     28 Input
     29 
     30 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Then follows the description of the test cases.
     31 
     32 The first line of each test case contains two integers $n$ and $k$ ($2 \leq n \leq 10^5$, $2 \leq k \leq 5$) — the size of the array $a$ and the number $k$.
     33 
     34 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10$).
     35 
     36 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     37 
     38 Output
     39 
     40 For each test case, output the minimum number of operations needed to make the product of all the numbers in the array divisible by $k$.
     41 
     42 Example
     43 
     44 Input
     45 
     46 ```
     47 15
     48 
     49 2 5
     50 
     51 7 3
     52 
     53 3 3
     54 
     55 7 4 1
     56 
     57 5 2
     58 
     59 9 7 7 3 9
     60 
     61 5 5
     62 
     63 5 4 1 2 3
     64 
     65 7 4
     66 
     67 9 5 1 5 9 5 1
     68 
     69 3 4
     70 
     71 6 3 6
     72 
     73 3 4
     74 
     75 6 1 5
     76 
     77 3 4
     78 
     79 1 5 9
     80 
     81 4 4
     82 
     83 1 4 1 1
     84 
     85 3 4
     86 
     87 3 5 3
     88 
     89 4 5
     90 
     91 8 9 9 3
     92 
     93 2 5
     94 
     95 1 6
     96 
     97 2 5
     98 
     99 10 10
    100 
    101 4 5
    102 
    103 1 6 1 1
    104 
    105 2 5
    106 
    107 7 7
    108 ```
    109 
    110 Output
    111 
    112 ```
    113 2
    114 2
    115 1
    116 0
    117 2
    118 0
    119 1
    120 2
    121 0
    122 1
    123 1
    124 4
    125 0
    126 4
    127 3
    128 ```
    129 
    130 Note
    131 
    132 In the first test case, we need to choose the index $i = 2$ twice. After that, the array will be $a = [7, 5]$. The product of all the numbers in the array is $35$.
    133 
    134 In the fourth test case, the product of the numbers in the array is $120$, which is already divisible by $5$, so no operations are needed.
    135 
    136 In the eighth test case, we can perform two operations by choosing $i = 2$ and $i = 3$ in any order. After that, the array will be $a = [1, 6, 10]$. The product of the numbers in the array is $60$.