POJ 2769 Reduced ID Numbers 同余定理

POJ 2769 Reduced ID Numbers 同余定理

Reduced ID Numbers Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 8989 Accepted: 3610

Description

T. Chur teaches various groups of students at university U. Every U-student has a unique Student Identification Number (SIN). A SIN s is an integer in the range 0 ≤ s ≤ MaxSIN with MaxSIN = 10⁶-1. T. Chur finds this range of SINs too large for identification within her groups. For each group, she wants to find the smallest positive integer m, such that within the group all SINs reduced modulo m are unique.

Input

On the first line of the input is a single positive integer N, telling the number of test cases (groups) to follow. Each case starts with one line containing the integer G (1 ≤ G ≤ 300): the number of students in the group. The following G lines each contain one SIN. The SINs within a group are distinct, though not necessarily sorted.

Output

For each test case, output one line containing the smallest modulus m, such that all SINs reduced modulo m are distinct.

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 
#include 
#include 

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