POJ2769 Reduced ID Numbers【同余定理】

题目链接:

?id=2769

题目大意:

有N个学生,每个学生有一个唯一的学生证号(0~10^6),但是为了学生证号的范围有点大,

所以希望找到一个最小的正整数M,使得所有学生的学生证号对模M均不同余。那么问题来

了:这个M是多少。

思路:

将M从1开始测试,,把所有学生证号对M取余的结果存起来,如果发现有相同的结果,就增

大M的值继续测试,直到满足所有学生的学生证号对M均不同余。

AC代码:

#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;bool p[100010];int Num[100010];int main(){int T,M,N;cin >> T;while(T–){cin >> N;for(int i = 0; i < N; ++i)cin >> Num[i];int flag;int M = 1;while(1){flag = 1;memset(p,0,sizeof(p));for(int i = 0; i < N; ++i){if(p[Num[i]%M]){flag = 0;break;}p[Num[i]%M] = 1;}if(flag)break;M++;}cout << M << endl;}return 0;}

坐在外婆的沙滩,看最白的帆影。

POJ2769 Reduced ID Numbers【同余定理】

相关文章:

你感兴趣的文章:

标签云: