解题思路

设选择出的非空子序列元素和为 $S$，目标是最大化 $S \bmod k$。

由于子序列只要求保持相对顺序，但求和与顺序无关，所以本题本质上就是：

从数组中选一个非空子集，使得其元素和对 $k$ 取模尽量大。

状态设计

题目内容

给定一个长度为 $n$的整数数组 {$a_1,a_2,…,a_n$} 和一个正整数 $k$。请选择一个非空子序列（不要求连续），将其元素之和对$k$ 取模，得到一个位于$[0,k)$的整数。请计算这个值的最大可能结果。

非空子序列指从原数组中删除任意个（可以为零，但不能全部）元素后得到的新序列，保持原相对顺序，但不要求连续。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤2×10^4)$表示数据组数。此后对每组数据：

• 第一行输入两个整数 $n,k(1≤k≤n≤2×10^4)$；
• 第二行输入$n$个整数$a_1,a_2,…,a_n(1≤a_i≤10^9)$。

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

输出描述

对于每一组测试数据，新起一行输出一个整数，表示选择某个非空子序列后，其元素之和对 $k$ 取模所得的最大值。

样例1

输入

3
5 5
3 8 2 6 4
5 5
5 10 15 20 5
3 4

输出

4
0
3

说明

对于第$1$组：例如选择子序列{$4$}，其和为$4$，对$5$取模为$4$，这是可能的最大值(也可选择{$3,6$}，其和为$9$，对$5$取模为$4$)。

对于第$2$组：所有元素均为$5$的倍数，任意非空子序列的和也是$5$的倍数，最大取模结果为$0$。

对于第$3$组：选择{$3$}或{$1,2$}的和对$4$取模均为$3$，为最大值。