From lyh 学长

2018.5.3 信(liang)心(liang)杯T3

一道略弱的数论题。

 

 

题目描述

给定 n个数，问是否能从中选出恰好 k个数，使得这些数两两之差可以被 m 整除。

输入输出格式

输入格式：

 

第一行输入三个正整数 n，k，m。

接下来一行 n个正整数。

输出格式：

 

若不能选出 k个数，则输出"No "（不包含引号）。

若可以，第一行输出" Yes"（不包含引号），第二行输出 k个正整数，用空格隔开，如果有多种方案，输出字典序最小的方案。

样例一

输入：3 2 3 1 8 4

输出：Yes

      1 4

样例二

输入：3 3 3 1 8 4

输出：No

样例三

输入：4 3 5 2 7 7 7

输出：Yes

     2 7 7

解析

可用简单同余知识来处理然而我考试时是用DP做的。

一道略弱的数论题。

若两数之差被m整除，则这两个数关于m同余。

轻松解出。

1 #include
      
        2 using namespace std; 3 int main(){ 4     int al[1000002],bl[1000002],cl[1000002],m,n,k,l=0,q; 5     scanf("%d%d%d",&n,&k,&m); 6     for(int i=1;i<=n;i++) 7         scanf("%d",&al[i]); 8     sort(al+1,al+1+n); 9     for(int i=1;i<=n;i++)10         cl[i]=al[i]%m;11     for(int i=1;i<=n;i++)12         bl[cl[i]]++;13     for(int i=1;i
       
        =k){15             cout<<"Yes"<