题目描述

小红最近闲来没事，于是他报名了高级软考，但是高级软考难度比较大，于是小红制定了一个刷题计划，他找到了 $n$ 套试卷，每套试卷的题目数量为$a_i$。小红每天上午最多打开一套试卷，下午最多打开一套试卷，也可以选择不刷题而摸鱼(当然不能上下午都摸鱼！)。当小红打开一套试卷后，他就会把上面的题目全部刷完。但是小红有强迫症，他希望每天刷的题目总数均为 $k$ 的倍数。请你计算小红最多能刷多少天的题?

输入描述

输入第—行为两个正整数n和k。

输入第二行为n个正整数ai

其中，$1$ $\leq$ $n$ $\leq$ $10^{5}$ , $1$ $\leq$ $k$, $a_i$ $\leq$ $10^{9}$

输出描述

一个整数，代表小红最多能刷题的天数

示例1

输入

6 4
1 1 2 2 3 4

输出

3

说明：

第一天上午刷 $1$ 号试卷，下午刷 $5$ 号试卷 ,总共刷 $4$题

第二天上午摸鱼，下午刷 $6$ 号试卷，总共刷 $4$ 题。

第三天上午刷 $3$号试卷，下午刷$4$号试卷，总共刷 $4$ 题

示例2

输入

5 7
1 2 3 3 3

输出

0

显然，小红没有任何一个方案可以进行刷题。

思路：贪心+哈希表

首先，我们可以使用哈希表去统计题目数量$\%k$的元素数量

对于一道题目，如果它本身就已经是$k$的倍数，那么为了尽可能多刷，一天只刷一套即可满足条件

其他的情况，就需要凑出来两套卷子$a,b$,保证$a+b$是$k$的倍数，其实就是取哈希表中$min(mp[a],mp[k-a])

代码

C++