solution.md

# 倍数问题

**题目描述**

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

**输入格式**

从标准输入读入数据。
第一行包括 2 个正整数 n, K。
第二行 n 个正整数，代表给定的 n 个数。

**输出格式**

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

**样例输入**

```
4 3
1 2 3 4
```

**样例输出**

```
9
```

**样例解释**

```
选择2、3、4。
```

以下<span style="color:red">错误</span>的一项是？

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```

### after

```cpp

```

## 答案

```cpp
#define ll long long
using namespace std;

const int maxx = 1e5 + 100;
const int maxm = 1e3 + 100;
int a[maxx];
vector<int> p[maxm];
int n, k;

bool cmp(int a, int b) { return a > b; }
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        p[a[i] % k].push_back(a[i]);
    }
    for (int i = 0; i < k; i++)
        sort(p[i].begin(), p[i].end(), cmp);
    int _max = 0;
    for (int i = 0; i < k; i++)
    {
        if (p[i].size() == 0)
            continue;
        if ((3 * i == k || i == 0) && p[i].size() >= 3)
            _max = max(_max, p[i][0] + p[i][1] + p[i][2]);
        for (int j = 0; j < k; j++)
        {
            if (!p[j].size())
                continue;
            int z = k - (i + j) % k;
            if (z < 0)
                continue;
            if (z == i && z == j)
                continue;
            else if ((i != j) && (z == i || z == j) && p[z].size() >= 2)
                _max = max(_max, p[i][0] + p[j][0] + p[z][1]);
            else if (i == j && p[i].size() >= 2 && p[z].size() >= 1)
                _max = max(_max, p[i][0] + p[j][1] + p[z][0]);
            else if (i != j && i != z && j != z && p[i].size() >= 1)
                _max = max(_max, p[i][0] + p[j][0] + p[z][0]);
        }
    }
    printf("%d\n", _max);
    return 0;
}

```
## 选项


### A

```cpp
#define FOR0(a, b) for (int i = a; i < b; ++i)
#define FORE(a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<int, int> pii;

ll dp[2][4][1005];
int n, k, a[100005], v[100005];
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);
        v[i] = a[i];
        v[i] %= k;
    }
    memset(dp, -0x3f3f3f3f, sizeof dp);
    dp[0][0][0] = 0;
    int d = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < k; ++j)
        {
            for (int p = 0; p <= 3; ++p)
            {
                if (i < p)
                    continue;
                dp[d ^ 1][p][j] = max(dp[d ^ 1][p][j], dp[d][p][j]);
                if (p > 0)
                    dp[d ^ 1][p][j] = max(dp[d ^ 1][p][j], dp[d][p - 1][((j - v[i]) % k + k) % k] + a[i]);
            }
        }
        d ^= 1;
    }
    cout << dp[d][3][0] << endl;
    return 0;
}
```

### B

```cpp
int n, k, ans = 0;
int temp[3], num[100005], vis[100005] = {0};

void dfs(int s)
{
    if (s == 3)
    {
        int t = temp[0] + temp[1] + temp[2];
        if (t % k == 0 && t > ans)
            ans = t;
        return;
    }
    else
    {
        for (int i = 0; i < n; i++)
        {
            if (!vis[i])
            {
                temp[s] = num[i];
                vis[i] = 1;
                dfs(s + 1);
                vis[i] = 0;
            }
        }
    }
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d", &num[i]);
    dfs(0);
    printf("%d\n", ans);
    return 0;
}
```

### C

```cpp
int N, k;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> k;
    vector<vector<int>> vec(k, vector<int>(3, -1));
    for (int i = 0; i < N; ++i)
    {
        int temp;
        cin >> temp;
        int y = temp % k;
        if (temp > vec[y][0])
        {
            vec[y][2] = vec[y][1];
            vec[y][1] = vec[y][0];
            vec[y][0] = temp;
        }
        else if (temp > vec[y][1])
        {
            vec[y][2] = vec[y][1];
            vec[y][1] = temp;
        }
        else if (temp > vec[y][2])
            vec[y][2] = temp;
    }

    vector<int> ans(3);
    int result = 0;
    for (int i = 0; i < k; ++i)
        for (int j = i; j < k; ++j)
        {
            int r = (k - i + k - j) % k;
            ans[0] = vec[i][0];
            if (i == j)
            {
                ans[1] = vec[i][1];
                if (r == i)
                    ans[2] = vec[i][2];
                else
                    ans[2] = vec[r][0];
            }
            else
            {
                ans[1] = vec[j][0];
                if (r == i)
                    ans[2] = vec[i][1];
                else if (r == j)
                    ans[2] = vec[j][1];
                else
                    ans[2] = vec[r][0];
            }
            if (ans[0] != -1 && ans[1] != -1 && ans[2] != -1 && ans[1] + ans[2] + ans[0] > result)
                result = ans[1] + ans[2] + ans[0];
        }
    cout << result;
}
```