众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。

但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。

现在小葱给了你 n 个数，希望你从这 n 个数中找到三个数，使得这三个数的和是 K 的倍数，且这个和最大。

数据保证一定有解。

输入格式

第一行包括 2 个正整数 n, K。

第二行 n 个正整数，代表给定的 n 个数。

输出格式

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

数据范围

1≤n≤105,
1≤K≤103,
给定的 n 个数均不超过 108

输入样例：

4 3
1 2 3 4

输出样例：

9

暴力枚举 O(n ^ 3) 过一半数据

思路：

纯暴力，排序后、分别从后往前枚举第1、2、3个数，找出符合条件的最大值

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;
typedef long long LL;
int n, m;

LL q[N];
int main(){
    cin >> n >> m;
    //cout << k << endl;
    for(int i = 1; i <= n; i++) scanf("%lld", &q[i]);
    sort(q + 1, q + n + 1);
    //printf("%d %d %d\n", q[n], q[n - 1], q[n - 2]);
    LL res = 0;
    for(int i = n; i > 0; i--){
        bool flag = false;
        for(int j = i - 1; j > 0; j--){
            for(int k = j - 1; k > 0; k--){
                LL t = q[i] + q[j] + q[k]; 
                //printf("%d %d %d\n", q[i], q[j], q[k]);
                if(t % m == 0){
                    //cout << k << endl;
                    res = max(t, res);
                    flag = true;
                    break;
                }
            }
            if(flag){
                break;
            }
        }
        if(flag){
            break;
        }
    }
    cout << res;
    return 0;
}

枚举 + 取模优化

思路 ：

由取模的性质可以知道， 若 (a + b + c) % m = 0, 则 (a % m + b % m + c % m ) % m = 0; 那么就可以通过枚举 a, b的余数，然后计算出 c 的余数。每次选择对应余数的最大值，又由于同一个数不能用两次，所以需要对i、j、t的相等情况进行判断。

t的计算过程如下：
设 i = a % m, j = b % m, t = c % m ，则 0 <= i, j, t < m,即 0 <= i + t + j < 3m
代入上式 (i + j + t) % m = 0,
则 i + j + t = 0 或者 i + j + t = m 或者 i + j + t = 2m;

故 取正余数 t = (m - (i + j) % m + m) % m

1. 先进行预处理，将每个数对 m 取模，然后存入相应的数组中
2. 对每个数组进行排序（排序方法任意）
3. 枚举第1、2个数对 m 取模的值，计算第三个数对 m 取模的结果
4. 进行特判
5. 更新res

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

const int N = 1010;

vector<int> a[N];

int n, m;
int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        int t;
        scanf("%d", &t);
        a[t % m].push_back(t);
    }
    for(int i = 0; i < m; i++){
        sort(a[i].begin(), a[i].end());
    }
    int res = 0;
    for(int i = 0; i < m; i++){
        for(int j = 0; j < m; j++){
            int t = (m - (i + j) % m + m) % m;
            //printf("%d %d %d\n",i, j, t);
            if(a[i].size()&&a[j].size()&&a[t].size()){
                int b = *(a[i].end() - 1),c, d;
                if(i != j&&j != t&& i != t){
                    c = *(a[j].end() - 1);
                    d = *(a[t].end() - 1);
                    //printf("%d %d %d %d\n", res, i, j, t);
                }else if(i == j&&j != t){
                    if(a[i].size() <= 1) continue;
                    c = *(a[i].end() - 2);
                    d = *(a[t].end() - 1);

                }else if(j == t&&i != t){
                    if(a[j].size() <= 1) continue;
                    c = *(a[j].end() - 1);
                    d = *(a[j].end() - 2);

                }else if(i == t&& j != t){
                     if(a[i].size() <= 1) continue;
                    d = *(a[i].end() - 2);
                    c = *(a[j].end() - 1);
                    //printf("%d %d %d %d\n", res, b, c, d);
                }else{
                    if(a[i].size() <= 2) continue;
                    c = *(a[i].end() - 2);
                    d = *(a[i].end() - 3);
                }
                int u = b + c + d;
                if(u >= res){
                    res = u;
                   // printf("%d %d %d %d\n", res, i, j, t);
                }
                //res = max(res, u);
            }
        }
    }
    cout << res;
    return 0;
}

dp + 取模优化

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1010;

int n, m;
vector<int> a[N];
int f[4][N];

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 0; i < n; i ++ )
    {
        int x;
        scanf("%d", &x);
        a[x % m].push_back(x);
    }

    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;

    for (int i = 0; i < m; i ++ )
    {
        sort(a[i].begin(), a[i].end());
        reverse(a[i].begin(), a[i].end());

        for (int u = 0; u < 3 && a[i].size(); u ++ )
        {
            int x = a[i][u];
            for (int j = 3; j >= 1; j -- )
                for (int k = 0; k < m; k ++ )
                    f[j][k] = max(f[j][k], f[j - 1][(k - x % m + m) % m] + x);
        }
    }

    printf("%d\n", f[3][0]);

    return 0;
}