题目描述
众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。现在小葱给了 n 个数，希望你从这 n 个数中找到三个数，使得这三个数的和是 K 的倍数，且这个和最大。数据保证一定有解。

输入描述
第一行包括 2 个正整数 n,K。
第二行 n 个正整数，代表给定的 n 个数。
其中，1\le n \le 10^5,\ 1\le K \le 10^3，给定的 n 个数均不超过 10^8。

输出描述
输出一行一个整数代表所求的和。

输入输出样例
示例
输入
4 3
1 2 3 4
输出
9

运行限制
最大运行时间：1s
最大运行内存: 256M

这个题目需要构造，而不是盲目的穷举，我们通过对余数进行分析可以知道下面这个结论：

我们设a = nk+p, b = nk+q,c = nk+r ,其中p,q,r分别为a,b,c的余数

我们假设a,b,c的和与k的余数是0，也就是

(a+b+c)%k=0

(3*nk+p+q+r)%k = 0

显然3*nk是可以被k整除的，要想让整式被k整除，那么p+q+r也必须被k整除，即

p+q+r = k

每个数的k的余数不可能大于k，这个是既定事实(如果大于k，那么里面k要被整除掉，只留下小于k的那部分余数)

所以要想取得三个数，使得他们的求和最大，那么可以转变为求得三个余数之和是k的数且数的求和最大的三个数

那么我们得对两个问题逐个解决:

1.怎么求三个余数之和是k的数

2. 怎么确保三个数的求和最大

解决1：a.使用余数桶存放余数，余数桶是一个二维数组，这个数组一维部分是每个可能的余数，这个数组的二维部分是取得这个余数的整数……解决余数存储问题，设余数桶为mod[1000]

b.三个余数之和是k，那么有四种情况:

r1 = r2 = r3(三个余数都相同)

r1 != r2 = r3(r2与r3相同，r1不等于r2与r3)

r1 = r2 != r3(r1与r2相等.而r2不等于r3)

r1 != r2 != r3(r1,r2,r3互不相同)，

我们先从0到k遍历r1,然后再嵌套一个从r1遍历到k的r2,再嵌套一个从r2遍历到k的r3的循环

用这种方法而不三层从0到k的for循环是因为，k最大的取值为 10^3，三层嵌套的时间复杂度为O(n^3)=10000000000，高达100亿，这显然会超时的，结合题目(mod[1],mod[2],mod[3])与(mod[2],mod[1],mod[3])并无不同，我们关心的只是 这三个数相加是否是k而不关心他们的先后顺序，也就是说mod[1]+mod[2]+mod[3]与mod[2]+mod[1]+mod[3]都等于k，他们是等价的，所以我们在循环中加入限制，只允许r1<r2<r3,这种方法能够遍历全部等可能的余数组合的原理是:

以1,2,3为例，它有多种出现方式:(1,2,3)，(1，3，2),(2,3,1),(2,1,3)等，但是无一例外的是，他们从小到大依次排序的结果只有一个(1,2,3)，因为我们只关心组合而不关系排列，所以我们限定一个从小到大的循环就可以覆盖到全部结果了

在循环中添加判断，判断上面的四种情况，每种情况要确保余数桶里面有足够数量的元素，判断为真的元素赋值给s,再在循环的最后命令一个判断 if(s>ans)ans = s，这样子做能够保证了ans始终是最大的（如果s比ans小，那么不会赋值，ans最大，如果s比ans大，那么s赋值给ans,ans最大）

解决2:

首先我们先对全部输入的数进行从大到小排序，然后在判断余数的时候，增加一个计数数组用于统计该余数已经有多少个了，我们从大到小一次判断余数，当计数器未满3的时候，写入余数桶，当计数器满3时，停止写入，计数器之所以取3是因为当r1=r2=r3的时候，要求余数桶里面有最少得有3个数。因为已经排序的原因，所以写入 的3个余数对应的数一定是前三大的数。

综上我们就解决了这个问题。

以下为具体代码

<code>#include <stdio.h>
#include <stdlib.h>
long long int list[100000];//放数的
long long int mod[1005][3];//余数桶，k<=1000，不用开十万
int cnt[1005] = {0};//余数r中存了几个数
int cmp_ll(const void *a, const void *b)
{
    long long x = *(long long *)a;
    long long y = *(long long *)b;
    if (x > y) return -1;
    if (x < y) return 1;
    return 0;
}
int main(void)
{
	long long int n,k,x,y,i;
	scanf("%lld %lld",&n,&k);
	for(x=0;x<n;x++)
	{
		scanf("%lld",&list[x]);
	}
	qsort(list,n,sizeof(long long),cmp_ll);//从大到小排序
	
	for(i = 0; i < 1005; i++)
	{
	    mod[i][0] = -1;
	    mod[i][1] = -1;
	    mod[i][2] = -1;
	}//初始化桶 
	
	for(x=0;x<n;x++)
	{
		long long int temp = list[x];
		int r = temp%k;
		if(cnt[r] < 3)
		{
			mod[r][cnt[r]] = temp;
			cnt[r] ++;
		}
	}//每个余数桶只保留该余数下最大的三个数
	long long ans = 0;
	int r1,r2,r3;
	//分四种情况：
	//情况1：r1=r2=r3，三个余数全部相同
	//情况2：r1=r2!=r3，前两个余数相同，第三个不同
	//情况3：r1!=r2=r3，后两个余数相同，第一个不同
	//情况4：r1!=r2 && r2!=r3，三个余数全都不同
	// r1<=r2<=r3 减少重复枚举，防止超时
	for(r1=0;r1<k;r1++)
	{
		for(r2=r1;r2<k;r2++)/*我们要找的只是**余数三元组 {r?, r?, r?} 的组合**，不在乎顺序：
`(1,2,3)`、`(2,1,3)`、`(3,1,2)` 这一堆，**它们三个余数相加的和完全一样**，`(r1+r2+r3)%K` 的结果也一模一样，算出来的总和也是同一个。
原来写法把同一种搭配翻来覆去算很多次，纯纯做重复无用功，浪费时间*/
		{
			for(r3=r2;r3<k;r3++)
			{
			    long long s = 0; // 每次一组余数，s重置为0！
			    // 先判断三个余数之和模k是否等于0，不满足直接跳过
			    if( (r1 + r2 + r3) % k != 0 )
			        continue;
			        
				if(r1==r2 && r2==r3)
				{
					if(cnt[r1]>=3)//确保这个余数桶里面有至少3个数可以取 
					{
						s = mod[r1][0] + mod[r2][1] + mod[r3][2];
					}
					else continue;//如果不符合有数可取，那么跳过本轮循环 
				}
				else if(r1==r2 && r2!=r3)
				{
					if(cnt[r1]>=2 && cnt[r3]>=1)
					{
						s = mod[r1][0] + mod[r1][1] + mod[r3][0];
					}
					else continue;
					
				}
				else if(r1!=r2 && r2 == r3)
				{
					if(cnt[r1]>=1 && cnt[r2]>=2)
					{
						s = mod[r1][0] + mod[r2][0] + mod[r2][1];
					}
					else continue;
				}
				else if(r1!=r2 && r2!=r3)
				{
					if(cnt[r1]>=1 && cnt[r2]>=1 && cnt[r3]>=1)
					{
						s = mod[r1][0] + mod[r2][0] + mod[r3][0];
					}
					else continue;
				}
				
				if(s>ans) ans = s;//这里筛选出最大的一个和 
				
			}
		}
	} 
	printf("%lld",ans); 
	
	
	return 0;
}
</code>