河南省第十届省赛 最小秘钥

时间:2022-09-10 14:51:02

title: 最小秘钥 河南省第十届省赛
tags: [省赛]

题目描述:

在中国近代史上,暂编军绝对是一支能打硬仗,大名鼎鼎的行动部队。“一二八”上海抗战,暂编军就曾打得小日本四易主帅。

号,暂编 军计划组成一个行动大队,派出N名队员潜伏在地,发动一次大规模的巷战行动。每名队员有自己的代号Ai,为了更好的配合作战,他们需要获得一个密钥Key,  然后各自迅速移动到Ai  MOD  Key位置,时刻一起开战。

作战方案已经定好,你能帮***行动大队快速找个满足条件的最小密钥Key吗?

MOD表示取模运算,要求不能有多名队员待在同一个位置。

输入:

第一行: T        表示以下有T组测试数据             ( 1≤T ≤5 )

对每组数据,  

第一行:N     表示行动人员数  (1<=N<=3000)

接下来一行有N个整数,分别表示每个队员的代号Ai       (1<=Ai<=20000)

输出:

对每组测试数据,输出占一行,一个整数 Key.  

样例输入:

2
3
1 2 3
5
4 6 9 10 13

样例输出:

3
8

分析:

看题目上说的一大堆,其实题意就是在给出的一系列的数中,找到一个数,使这些数对它取余,余数没有冲突。

代码:

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
    int T,n,num[3009];
    scanf("%d",&T);
    int A[20009];
    while(T--)
    {
        int n,flag=0;
        scanf("%d",&n);
        for(int i=0; i<n; i++)
            scanf("%d",&num[i]);
        for(int i=n;; i++)
        {
            flag=0;
            memset(A,0,sizeof(A));
            for(int j=0; j<n; j++)
            {
                int op=num[j]%i;
                if(A[op]==0)
                    A[op]=1;
                else
                {
                    flag=1;///有冲突的
                    break;
                }
            }
            if(flag==0)///没有冲突
            {
                printf("%d\n",i);///直接输出来
                break;///也没有必要往下找了
            }
        }
    }
    return 0;
}