思路：思维

首先计算每个数的个数 $cnt$。

$single[i]$ 为每个模 $m$ 的数为 $i$ 的数中，数量为奇数的个数

$all[i]$ 为每个模 $m$ 的数的偶数部分的数的个数。

然后先拿 $single[i]$ 和 $single[m - i]$ 匹配。
多的一方如果是 $single[i]$ ，则继续和 $all[m - i]$ 尝试匹配。
多的一方如果是 $single[m-i]$ ，则继续和 $all[i]$ 尝试匹配。

最后所有相同的数进行匹配即可。

时间复杂度：$O(n)$

代码

C++

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

const int MAXN = 100001;

void solve() {
    int n, m;
    cin >> n >> m;

    vector<int> x(n);
    for (int i = 0; i < n; ++i) cin >> x[i];

    vector<int> cnt(MAXN);
    // 模 m 为 0 的数，这些数两两配对即可
    int r0 = 0;
    for (int i = 0; i < n; ++i) {
        if (x[i] % m == 0) r0 += 1;
        else cnt[x[i]] += 1;
    }

    // m 的倍数，两两配对即可，因为他们相加必然是 m 的倍数
    int ans = r0 / 2;

    


    vector<int> single(m);
    vector<int> all(m);
    for (int i = 1; i < MAXN; ++i) {
        int last = cnt[i];
        // 如果 i 的个数 cnt[i] 为奇数，则给 single[i % m] 加 1
        if (cnt[i] % 2 == 1) {
            single[i % m] += 1;
            last -= 1;
        }
        // i 的个数加上 cnt[i] ，如果 cnt[i] 为奇数，则去掉 1 
        all[i % m] += last;
    }

    // 将落单的数中的偶数个 idx 与 all[m - idx] 中的数配对
    auto get = [&](int idx) {
        int last = single[idx];
        if (single[idx] & 1) last -= 1;
        int need = min(single[idx], all[m - idx]);
        all[m - idx] -= need;
        return need;
    };

    // 优先将落单的数进行配对
    for (int i = 1, j = m - 1; i <= j; ++i, --j) {
        if (i < j) {
            // i 和 j 落单数先匹配
            int need = min(single[i], single[j]);
            ans += need;
            single[i] -= need;
            single[j] -= need;
            // 如果 single[i] > single[j]
            if (single[i] > 0) {
                // 尝试数 i 和 all 中的数 m-i 匹配
                ans += get(i);
            } else if (single[j] > 0) {
                // 如果 single[i] < single[j]
                // 尝试数 j 和 all 中的数 m-j 匹配
                ans += get(j);
            }
        } else {
            // 如果 i==j，则其落单的数自己和自己匹配
            ans += single[i] / 2;
        }
    }

    // 最后将 all 中的数除 2 累加到答案中，即相同的数匹配
    for (int i = 0; i < m; ++i) ans += all[i] / 2;

    cout << ans << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) solve();

    return 0;
}

python

MAXN = 100001
cnt = [0] * MAXN


def solve():
    n, m = map(int, input().split())

    x = list(map(int, input().split()))

    i = 0
    while i < MAXN:
        cnt[i] = 0
        i += 1

    r0 = 0
    for i in range(n):
        if x[i] % m == 0:
            r0 += 1
        else:
            cnt[x[i]] += 1

    ans = r0 // 2

    single = [0] * m
    all_nums = [0] * m
    for i in range(1, MAXN):
        last = cnt[i]
        if cnt[i] % 2 == 1:
            single[i % m] += 1
            last -= 1
        all_nums[i % m] += last

    def get(idx):
        last = single[idx]
        if single[idx] & 1:
            last -= 1
        need = min(single[idx], all_nums[m - idx])
        all_nums[m - idx] -= need
        return need
    i, j = 1, m - 1
    while i <= j:
        if i < j:
            need = min(single[i], single[j])
            ans += need
            single[i] -= need
            single[j] -= need
            if single[i] > 0:
                ans += get(i)
            elif single[j] > 0:
                ans += get(j)
        else:
            ans += single[i] // 2
        i += 1
        j -= 1

    for i in range(m):
        ans += all_nums[i] // 2

    print(ans)


T = int(input())


for _ in range(T):
    solve()

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static final int MAXN = 100001;
    static int[] cnt = new int[MAXN];

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(reader.readLine());

        for (int t = 0; t < T; t++) {
            solve(reader);
        }
    }

    static void solve(BufferedReader reader) throws IOException {
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int n = Integer.parseInt(tokenizer.nextToken());
        int m = Integer.parseInt(tokenizer.nextToken());

        int[] x = new int[n];
        tokenizer = new StringTokenizer(reader.readLine());
        for (int i = 0; i < n; i++) {
            x[i] = Integer.parseInt(tokenizer.nextToken());
        }

        for (int i = 0; i < MAXN; i++) {
            cnt[i] = 0;
        }

        int r0 = 0;
        for (int i = 0; i < n; i++) {
            if (x[i] % m == 0) {
                r0 += 1;
            } else {
                cnt[x[i]] += 1;
            }
        }

        int ans = r0 / 2;

        int[] single = new int[m];
        int[] all_nums = new int[m];
        for (int i = 1; i < MAXN; i++) {
            int last = cnt[i];
            if (cnt[i] % 2 == 1) {
                single[i % m] += 1;
                last -= 1;
            }
            all_nums[i % m] += last;
        }

        int i = 1;
        int j = m - 1;
        while (i <= j) {
            if (i < j) {
                int need = Math.min(single[i], single[j]);
                ans += need;
                single[i] -= need;
                single[j] -= need;
                if (single[i] > 0) {
                    ans += get(i, m, single, all_nums);
                } else if (single[j] > 0) {
                    ans += get(j, m, single, all_nums);
                }
            } else {
                ans += single[i] / 2;
            }
            i += 1;
            j -= 1;
        }

        for (int k = 0; k < m; k++) {
            ans += all_nums[k] / 2;
        }

        System.out.println(ans);
    }

    static int get(int idx, int m, int[] single, int[] all_nums) {
        int last = single[idx];
        if ((single[idx] & 1) != 0) {
            last -= 1;
        }
        int need = Math.min(single[idx], all_nums[m - idx]);
        all_nums[m - idx] -= need;
        return need;
    }
}

题目内容

小红有 $n$ 个数，第 $i$ 个数为 $x_i$ ，他想将这些数两两配对。

现在小红给定了两个数配对的条件：

• 两个数相同，可以配对
• 两个数的和为 $m$ 的倍数，也可以配对

满足上面两个条件之一，即可配对。

现在小红问你，他可以最多配对出多少个数对。

输入描述

第一行，一个整数 $T(1\leq T\leq 10)$ ，表示数据组数。

接下来每组数据，

第一行，两个整数 $n(2\leq n\leq 10^5)$ 和 $m(1\leq m\leq 10^5)$ 。

第二行，$n$ 个整数 $x_i(1\leq x_i\leq 10^5)$ 。

输出描述

一个整数，表示小红可以配对的最大对数。

样例

输入

1
9 8
9 9 8 2 4 4 3 5 3

输出

3

说明

9 和 9 配对 4 和 4 配对 3 和 5 配对