解题思路

只关心 $a_i \bmod k$。余数 $0$ 的检测单可以单独成一天。其余把余数 $a$ 与 $k-a$ 配对，每对一天；若 $2a\equiv 0\pmod k$ 则同余数组内两两配对。

复杂度分析

时间复杂度 $O(n)$，空间复杂度 $O(\min(n,k))$。

代码实现

题目内容

实验室有 $n$ 份检测单，第 $i$ 份包含 $a_i$ 个样本。每天上午至多安排一份、下午至多安排一份，且当天不能两个工位都空着。当天实际处理的样本数之和必须是 $k$ 的倍数。每份检测单最多使用一次，一旦安排就必须整份做完。

请计算最多可以安排多少天。

约束：$1 \le n \le 100000$，$1 \le k,a_i \le 1000000000$。

输入描述

第一行包含两个正整数 $n$ 和 $k$，分别表示检测单份数与倍数要求，满足 $1 \le n \le 100000$，$1 \le k \le 1000000000$。

第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$，满足 $1 \le a_i \le 1000000000$。

输出描述

输出一个整数，表示最多可以安排的天数。

样例1

输入

4 5
2 3 7 8

输出

2

说明

对 $k=5$ 取模后得到 2,3,2,3。

2 与 3 可以两两配对，共两对，因此最多安排 2 天。

样例2

输入

3 2
4 6 9

输出

2

说明

模 2 后为 0,0,1。余数为 0 的任务可以单独占一天（另一个班次空着），共 2 天；余数 1 无法配对。

样例3

输入

1 10
20

输出

1

说明

唯一任务的工作量是 10 的倍数，单独安排一天即可。

样例4

输入

7 6
1 5 11 12 13 7 18

输出

4

说明

模 6 后可分成：余 0 的单独使用，以及余数互补的配对。

最多得到 4 天。