codeforces-scrape

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

1497B.md (1648B)


      1 Source: https://codeforces.com/problemset/problem/1497/B
      2 
      3 B. M-arrays
      4 
      5 time limit per test
      6 
      7 1 second
      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 $a_1, a_2, \ldots, a_n$ consisting of $n$ positive integers and a positive integer $m$.
     22 
     23 You should divide elements of this array into some arrays. You can order the elements in the new arrays as you want.
     24 
     25 Let's call an array $m$-divisible if for each two adjacent numbers in the array (two numbers on the positions $i$ and $i+1$ are called adjacent for each $i$) their sum is divisible by $m$. An array of one element is $m$-divisible.
     26 
     27 Find the smallest number of $m$-divisible arrays that $a_1, a_2, \ldots, a_n$ is possible to divide into.
     28 
     29 Input
     30 
     31 The first line contains a single integer $t$ $(1 \le t \le 1000)$  — the number of test cases.
     32 
     33 The first line of each test case contains two integers $n$, $m$ $(1 \le n \le 10^5, 1 \le m \le 10^5)$.
     34 
     35 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le 10^9)$.
     36 
     37 It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases do not exceed $10^5$.
     38 
     39 Output
     40 
     41 For each test case print the answer to the problem.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 4
     49 6 4
     50 2 2 8 6 9 4
     51 10 8
     52 1 1 1 5 2 4 4 8 6 7
     53 1 1
     54 666
     55 2 2
     56 2 4
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 3
     63 6
     64 1
     65 1
     66 ```
     67 
     68 Note
     69 
     70 In the first test case we can divide the elements as follows:
     71 
     72 * $[4, 8]$. It is a $4$-divisible array because $4+8$ is divisible by $4$.
     73 * $[2, 6, 2]$. It is a $4$-divisible array because $2+6$ and $6+2$ are divisible by $4$.
     74 * $[9]$. It is a $4$-divisible array because it consists of one element.