H题: Hash Function

原题链接:https://ac.nowcoder.com/acm/contest/11166/H

题目大意

给定一个大小为 n ( 1 ≤ n ≤ 5 ⋅ 1 0 10 ) n(1≤n≤5·10^{10} ) n(1≤n≤5⋅1010)的集合 S = { a 0 , a 1 , . . . , a n − 1 } S=\{a_0,a_1,...,a_{n-1}\} S={a0​,a1​,...,an−1​}。
求最小的正整数 s e e d seed seed，使得对于任意 i ( 0 ≤ i ＜ n ) i(0\leq i＜n) i(0≤i＜n)， a i   m o d   s e e d a_i\bmod seed ai​modseed的结果各不相同。

题解

数据强度一般，采用优化版暴力做法。
因为有 n n n个数据，所以哈希域的大小应不小于 n n n，从 n n n开始往上枚举 s e e d seed seed，对于每个 s e e d seed seed进行判断。
对时间复杂度进行优化，不难发现，因为我们枚举的 s e e d seed seed是不断增大的，所以当一个数已经小于当前的 s e e d seed seed时，对于以后的任意一个更大的 s e e d seed seed，取模结果都是该数本身，即在以后的判断过程中，我们不需要对该数的取模结果进行计算。我们可以通过对数组进行排序，以优化初始化过程

参考代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5；
int n,a[MAXN],t=1;
int vis[MAXN];
void read(int &x){
    int ret=0;
    char c=getchar(),last;
    while(c<'0'||c>'9')last=c,c=getchar();
    while(c>='0'&&c<='9'){
        ret=ret*10+c-'0';
        c=getchar();
    }
    x=last=='-'?-ret:ret;
}//读入优化
bool check(int mod){
    for(int i=t;i<=n;i++){
        if(a[i]<mod&&vis[i]==0)vis[a[i]]=-1,t=i+1;//对于小于mod的数进行特殊标记，并记录下标，优化判断时的起始位置
        else if(vis[a[i]%mod]==0)vis[a[i]%mod]=1;//对于不小于mod的数计算取模值并标记
        else if(vis[a[i]%mod])//发现两数取模值相同
        {
            for(int j=t;j<i;j++)if(vis[a[j]%mod]!=-1)vis[a[j]%mod]=0;//将普通标记初始化
            return false;
        }
    }
    return true;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)read(a[i]);
    sort(a+1,a+n+1);//排序
    for(int i=n;;i++)if(check(i)){printf("%d\n",i);break;}//枚举，判断
    return 0;
}