题意

从给定 \(n\) 个数中选择 \(k\) 个数,使它们任意两数之差是 \(m\) 的约数。若存在,则输出 "Yes",并给出方案;否则,输出 "No"。

其中,\(2 \leq k \leq n \leq 10^5\)\(1 \leq m \leq 10^5\)\(0 \leq a_i \leq 10^9\)

题解

统计余数相同的数字个数。

代码

 1 2 3 4 5 6 7 8 910111213141516171819202122232425262728293031323334
#include <bits/stdc++.h>
const int MAX_N = 1e5 + 5;
const int MAX_M = 1e5 + 5;
int a[MAX_N], r[MAX_M];
int main() {
    int n, k, m;
    scanf("%d%d%d", &n, &k, &m);
    memset(r, 0, sizeof(r));
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), r[a[i] % m]++;
    int ans = -1;
    for (int i = 0; i < m; i++)
        if (r[i] >= k) {
            ans = i;
            break;
        }
    if (ans == -1) {
        printf("No\n");
        return 0;
    }
    printf("Yes\n");
    for (int i = 1, cnt = 0; i <= n; i++) {
        if (a[i] % m == ans) {
            if (!cnt)
                printf("%d", a[i]);
            else
                printf(" %d", a[i]);
            if (++cnt == k)
                break;
        }
    }
    printf("\n");
    return 0;
}
comments powered by Disqus