思路：哈希表 取模

我们可以创建一个哈希表，用于存储每个药丸疗效模$k$的结果的数量。

本题有两种情况

情况1：每个元素模$k$的结果都为$\frac{k}{2}$或者0，则这些元素都可以选择

情况2：两两元素的和模$k$的结果为0，则只能选这两个元素

根据上述情况对答案进行计算，更新最大值即可。

代码

C++

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

bool find_pair(vector<int>& a, int n, int k) {
	unordered_set<int> us;
	for (int i = 0; i < n; ++i) {
		if (us.count(k - a[i])) {
			return true;
		}
		us.insert(a[i]);
	}
	return false;
}

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	int multiple = 0, half = 0;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		a[i] %= k;
		if (a[i] % k == 0) {
			++multiple;
		} else if (k % 2 == 0 && a[i] % k == k / 2) {
			++half;
		}
	}
	if (max(multiple, half) >= 2) {
		cout << max(multiple, half) << endl;
	} else if (find_pair(a, n, k)) {
		cout << 2 << endl;
	} else {
		cout << -1 << endl;
	}
	return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        scanner.nextLine();
        int[] ints = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        HashMap<Integer, Integer> yushus = new HashMap<>();
        for (int i = 0; i < ints.length; i++) {
            yushus.put(ints[i]%k,yushus.getOrDefault(ints[i]%k,0)+1);
        }
        int maxCount=0;
        if(k%2==0){
            //中间或者余数为0的可以直接取
            int mi = k / 2;
            maxCount=Math.max(yushus.getOrDefault(mi,0),yushus.getOrDefault(0,0));
        }else {
            maxCount=yushus.getOrDefault(0,0);
        }
        if(maxCount<2){
            if(k%2==0){
                for (Integer integer : yushus.keySet()) {
                    if(integer!=k/2&&yushus.containsKey(k-integer)){
                        System.out.println(2);
                        return;
                    }
                }
            }else {
                for (Integer integer : yushus.keySet()) {
                    if(yushus.containsKey(k-integer)){
                        System.out.println(2);
                        return;
                    }
                }
            }
        }else {
            System.out.println(maxCount);
            return;
        }
        System.out.println(-1);
    }
}

python

from collections import defaultdict

cntMap = defaultdict(int)
n, k = map(int, input().split())
arr = list(map(int, input().split()))
for num in arr:
    cntMap[num % k] += 1
ans = 0
for num, cnt in cntMap.items():
    if num * 2 == k or num % k == 0:
        ans = max(ans, cnt)
    elif k - num in cntMap:
        ans = max(ans, 2)
print(ans if ans >= 2 else -1)

题目描述

塔某病了，你是远近闻名的神医，由于塔子经常干扰你刷每日委托，你打算借这个机会好好的斥候塔子。你准备了n粒药丸和一个目标疗效k，每一粒药丸疗效都被赋予了一个值，如果塔子能尽可能取出最多的药丸，使得任意两个药丸的疗效之和都是k的倍数。

古人云，今日留一面，他日好相见，救救塔子！（doge）

输入描述

第一行输入两个正整数n和k

第二行输入n个正整数$a_i$。代表塔子拿到的药丸

$1\le n\le 200000$

$1\le k,a_i\le 1e9$

输出描述

如果无法取不少于2个数，则直接输出-1。否则输出一个正整数，代表取出的数的最多数量.

样例

输入

5 5
2 1 10 5 3

输出

2

说明

选择数字2和3

Limitation

1s, 1024KiB for each test case.