[原创]POJ 2769 Reduced ID Numbers [同余]【数论】

2016-09-12 00:25:33 Tabris_ 阅读数：290

博客爬取于2020-06-14 22:43:22
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52509493

题目连接:http://poj.org/problem?id=2769
-------------------------------.
Reduced ID Numbers
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 9927 Accepted: 3960
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 = 106-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
Source

Northwestern Europe 2005

--------------------------------------.
题目大意：
就是给你N个数(ni<1e6) 找一个数使得这N个数都不同于这个数 输出最小的这个数

解题思路:
开始一顿推公式 推啊推 然后发现根本推不出来 ；
然后看了一下数据范围 发现N*1e6 时间给的就是2S 暴力就行了啊

然后就这样水过去了。。。。

从1开始枚举就行了 然后判断下所有数对其求余的值 然后hash记录一下 就能判断行不行了 行了就直接输出 不行就接着枚举 因为数值最大只有1e6 所以最后肯定有一个数能满足题意。。。。

最讨厌做这种暴力题目了 说难真不难 但是我这种ZZ根本不想搞暴力 结果就各种GG
其实还是思维定式太重了 想问题 越来越极限。。。

附本题代码
-----------------------------------------。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
# include <vector>
# include <queue>
# include <set>
# include <map>
# include <string>
# include <math.h>
# include <stdlib.h>
# include <time.h>
using namespace std;

/*********************INPUT*************************/
# define s2l(a,b)   scanf("%d%d",&a,&b)
# define s2_l(a,b)  scanf("%I64d%I64d",&a,&b)

/*********************OUTPUT*************************/
# define pr1l(a)    printf("%d",a);
# define pr1_l(a)   printf("%I64d",a);
# define pr1ll(a)   printf("%lld",a);
# define space      printf(" ");
# define line       printf("\n");

/****************************************/
# define _LL __int64
/****************************************/
# define fr(a,b,c)  for(int a=b;a<c;a++)
# define mem(a,b,c) for(int i=0;i<=c;i++)a[i]=b;
typedef long long int LL ;
# define INF 0x3f3f3f3f
# define pb push_back

# define lalal puts("*******");
/*************************************/

const int MOD = 1e9+7;
const int M = 1e5+10;

int a[M] , b[M];
int n;

bool check(int m)
{
    memset(b , 0 , sizeof(b));
    for(int i = 0 ; i < n ; i ++)
    {
        if(b[a[i] % m])
            return false;
        else
            b[a[i] % m] = 1;
    }
    return true;
}

int main()
{

    int _;
    while(scanf("%d",&_)!=EOF)
        while(_--)
        {
            scanf("%d",&n);
            for(int i = 0 ; i < n ; i ++)
                scanf("%d",&a[i]);

            for(int m = 1 ; m < M ; m ++)
            {
                if(check(m))
                {
                    printf("%d\n",m);
                    break;
                }
            }
        }
    return 0;
}