翻车

题目

【问题描述】
有一天，小武找到了翻车王，给了他n个整数a1,a2,a3,…an，翻车王
需要选择其中的k个数，使得选出的k个数中任意两个的差都可以被m整除。
选出的数可以重复，但不可以超过这n个数中该数的个数。
翻车王不想翻车，所以需要你的帮助。
【输入格式】
第一行包括3个整数n,k,m（2 ≤ k ≤ n ≤ 100000，1 ≤ m ≤ 100000），
n,k,m意义见题面。
第二行包括n个数a1,a2,a3,…an（0 ≤ ai ≤ 1000000000）。
【输出格式】
如果不可以选出k个数，使得选出这k个数中任意两个的差都可以被m整
除，那么输出“No”。
否则，在第一行输出“Yes”。在第二行输出这k个整数b1，b2，...bk
（所选的数字），两两数之间有一个空格。如果有多种选择k个数字的方案，
请输出任意一种。
【输入输出样例】
输入
4 3 5
2 7 7 7

输出
Yes
2 7 7

---

思路：

首先，我们想到，其实(x-y)%m==0就等价于x≡y(mod m)，所以我们可以先把a_i存起来，再通过他们模m用桶排，找到符合要求的一组数，输出k个。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[100001],b[100000],t;
int main()
{
    freopen("rollover.in","r",stdin);
    freopen("rollover.out","w",stdout);
    cin>>n>>k>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[a[i]%m]++;
    }
    for(int i=0;i<m;i++)
    {
        if(b[i]>=k)
        {
            cout<<"Yes"<<endl;
            for(int j=1;j<=n;j++)
            {
                if(a[j]%5==i)
                {
                    t++;
                    cout<<a[j]<<" ";
                    if(t==k) return 0;
                }
            }
            cout<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
    return 0;
}