| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 8989 | Accepted: 3610 |
Description
Input
Output
Sample Input
2
1
124866
3
124866
111111
987651
Sample Output
1
8
这道题是对同余定理的考查，思路很简单，暴力地枚举j，直到j满足集合中任意两个数对j取余都不相等，此时停止循环；
对于代码中的memset，比用for循环初始化为0快，只是在数组大的时候。在数组大小比较小时则for初始化比较省时（我在这超时了4、5次了）
一共是n个学生，所以去完模之后至少要有n个不同的值，所有程序里面的j要从n开始的。当然从1开始也不会错，只是一个小小的优化吧。
代码如下：
#include <stdio.h>
#include <string.h>
#include <math.h>
int a[10000001];
int main()
{
int i,j,n;
int cas,ans,t;
int s[303];
int f;
scanf("%d",&cas);
while(cas--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&s[i]);
for(j=n;j<1000000;j++)
{
f=0;
for(i=0;i<=j;i++) //这里用memset的话会超时的！
a[i]=0;
for(i=0;i<n;i++)
{
if(a[s[i]%j])
{
f=1;
break;
}
a[s[i]%j]=1;
}
if(!f)
break;
}
printf("%d\n",j);
}
return 0;
}
POJ 2769 Reduced ID Numbers 同余定理
原文：http://blog.csdn.net/u013068502/article/details/40190769