AOJ.1301 差除

题目

目描述

集合要满足互异性,即一个集合不能包含相同的元素。但是有的时候,我们需要集合中包含相同的元素,这种集合叫做多重集合(multiset)。
现在有一个多重集合,其中有n个整数。现在需要你从其中选出k个整数,使得k个数中任意两个的差都可以被m整除。
问题来了,能否从多重集合中找到k个数,若果可以的话,输出Yes,否则输出No。

程序输入说明

第一行,整数n,k,m,含义如题目所描述。
第二行,n个整数。
2<=k<=100000,1<=m<=100000

程序输出说明

如果能找到,则输出Yes,否则输出No

程序输入样例

3 2 3
1 8 4
3 3 3
1 8 4

程序输出样例

Yes
No

提示

对于第一组数据,可以找到两个数1、4,使得他们的差被3整除。输出Yes。
对于第二组数据,找不到3个数,使得两两之间差被3整除,输出No。

分析

这个题不能直接上子集树(最后两组数据量比较大),必须对\(O(N^{2})\)算法进一步优化。

考虑k个数中任意两个的差都能被m整除这一点:这代表这两个数mod m的值相同(若\(A\equiv B(MOD \: N)\),则\(A-B\equiv B-B(MOD \: N)\))。因此,只需要记录每个数mod m的值,如果从0~m-1的范围内有某项的值超过了k,即可以认定存在k个数两两之差均可被m整除。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
const int MAXM = 100010;
int ar[MAXM];
 
int main() {
    int n = 0, k = 0, m = 0;
 
    while(scanf("%d %d %d", &n, &k, &m) != EOF){
        memset(ar, 0, sizeof(ar));
         
        int tmp = 0;
        for(int i = 0; i < n; i++){
            scanf("%d", &tmp);
            ar[tmp % m]++;
        }
 
        bool flag = false;
        for(int i = 0; i < m; i++){
            if(ar[i] >= k){
                flag = true;
                break;
            }
        }
 
        printf(flag ? "Yes\n" : "No\n");
    }
 
    return 0;
}
updatedupdated2022-05-212022-05-21