将数组按余数分组：对每个数计算 $r = a_i \bmod k$ ，分类到 $V_r$ 。
对于 $r = 0$ 以及（若 $k$ 为偶数） $r = \frac{k}{2}$ ：同类元素可以两两配对移除，最多只能留下 $1$ 个。要最大化剩余和，应移除该类中最小的 $2 \left\lfloor \frac{|V_r|}{2} \right\rfloor$ 个元素。
对于互补余数对 $r$ 与 $s = (k-r) \bmod k$ （取 $1 \le r < s \le k-1$ ）：
- 最终必须让两类中至少有一类变为空，因此必然会从两边各移除 $m = \min(|V_r|, |V_s|)$ 个元素。
- 为使剩余和最大，移除两侧中最小的 $m$ 个元素（总移除和最小）。
- 余下的就是较大一侧的剩余元素（或两边都空）。

P3498.第2题-元素最大和

1000ms

Difficulty: 6

所属公司 : 饿了么

算法与标签>贪心算法

题目内容

给定一个长度为 $n$ 的正整数数组{ $a_1,a_2,...,a_n$ }，以及一个正整数 $k$ 。定义一次操作如下:

你必须重复执行操作，直到数组中不存在这样的两个元素 $a_u$ 和 $a_v$ ，使得它们的和能被整除为止。

此时数组长度减少若干，你需要最大化剩余元素之和。请计算并输出该最大和。

每个测试文件均包含多组测试数据。第一行输入一个整数 $t(1 ≦t≦10^4)$ 表示数据组数，每组测试数

据描述如下: 第一行输入两个整数 $n$ 和 $k(1≦n≦2×10^5，1≦k≦ 10^9)$

第二行输入 $n$ 个整数 $a_1,a_2,,..,a_n (1 ≦ a_i ≦ 10^9)$

除此之外，保证单个测试文件的n之和不超过 $2×10^5$

对于每一组测试数据，新起一-行，输出一个整数，表示满足条件的最大数组元素之和。

输入

输出

4 
3

输入

预期输出（选填）