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.