题意

从给定\(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 910111213141516171819202122232425262728293031
#include <cstdio>
#include <cstring>
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