题目地址

这是一道数论题目
要用到 同余定理
如果 a-b整除k 那么 a b对k同余

对于所有的输入值a[i]
所以要找到一个最小的数r
使得任意2个数的差不能整除r
易得 n<=r<=max(a[i])

先看数值范围 n<=5000 a[i]<=1000000
5000*5000/2>1000000
所以不能直接2个for循环 对每个差做判断 不然肯定超时
定义一个数组b[max(a[i])] 记录所有的差的绝对值
然后从大到小开始遍历改数组b
找出每个差的所有因素 将他们标记成非答案
然后从n开始搜索 找出最小的答案

为什么要从大到小开始遍历数组
因为大数的因素 就不用在遍历了 可以省一部分时间

#include <stdio.h>
#include <string.h>
#include <math.h>
int main(){
    int n;
    scanf("%d",&n);
    int i,j,k,l;
    int* input=new int[n];
    int max=0;
    for(i=0;i<n;i++)
    {
        scanf("%d",&input[i]);
        if(max<input[i])
        {
            max=input[i];
        }
    }
    int* result=new int[max+1];
    int* bjNum=new int[max+1];
    memset(result,0,(max+1)*sizeof(int));
    memset(bjNum,0,(max+1)*sizeof(int));
    result[1]=1;

    int* ss=new int[max/2+5];
    ss[0]=2;
    int len_ss=1;
    int max2=(int)sqrt(max);
    for(i=3;i<=max2;i++)
    {
        int tmp=(int)sqrt(i);
        int isSs=1;
        for(j=0;j<len_ss;j++)
        {   
            if(ss[j]>tmp)
            {
                break;
            }
            if(i%ss[j]==0)
            {
                isSs=0;
                break;
            }
        }
        if(isSs)
        {
            ss[len_ss]=i;
            len_ss++;
        }
    }

    int maxYsfj=(int)log(max)+1;
    int* ysfj=new int[maxYsfj];
    int* ysfj_num=new int[maxYsfj];
    int* dfs=new int[maxYsfj];
    int len_ysfj=0;

    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            int num=abs(input[j]-input[i]);
            bjNum[num]=1;
        }
    }

    for(i=max;i>=n;i--)
    {
        if(bjNum[i])
        {
            int num=i;
            len_ysfj=0;
            k=0;

            //因式分解
            while (num>=ss[k]&&k<len_ss)
            {
                if(num%ss[k]==0)
                {
                    
                    ysfj[len_ysfj]=ss[k];
                    ysfj_num[len_ysfj]=0;
                    do
                    {
                        num=num/ss[k];
                        ysfj_num[len_ysfj]++;
                    } while (num%ss[k]==0);
                    len_ysfj++;
                }
                k++;
            }
            if(num>1)
            {
                ysfj[len_ysfj]=num;
                ysfj_num[len_ysfj]=1;
                len_ysfj++;
            }

            //用因式分解的结果求出所有因素
            if(len_ysfj>0)
            {
                memset(dfs,0,len_ysfj*sizeof(int));
                k=0;
                while (k<len_ysfj)
                {
                    k=0;
                    dfs[0]++;
                    while (dfs[k]>ysfj_num[k])
                    {
                        dfs[k]=0;
                        k++;
                        if(k>=len_ysfj){
                            break;
                        }
                        dfs[k]++;
                    }
                    
                    if(k<len_ysfj)
                    {
                        num=1;
                        for(l=0;l<len_ysfj;l++)
                        {
                            num*=pow(ysfj[l],dfs[l]);
                        }
                        result[num]=1;
                        //大数的因数不用再重复处理了
                        bjNum[num]=0;
                    }
                   
                }
                
            }
            
        }
    }

    for(i=n;i<=max;i++)
    {
        if(!result[i])
        {
            printf("%d\n",i);
            break;
        }
    }

    delete input;
    delete result;
    delete bjNum;
    delete ss;
    delete ysfj;
    delete ysfj_num;
    delete dfs;
}