题目链接：点击查看

题目大意：给出一个长度为 n n n 的序列，现在要求找到一个 s e e d seed seed，使得所有数字变为 a [ i ] = a [ i ] m o d    s e e d a[i]=a[i]\mod seed a[i]=a[i]modseed 后两两互不相同，找到最小的 s e e d seed seed

题目分析：考虑转换模型，如果存在着 i i i 和 j j j 使得 a [ i ] ≡ a [ j ] ( m o d s e e d ) a[i] \equiv a[j] \pmod {seed} a[i]≡a[j](modseed)，那么肯定有 a [ i ] + k ∗ s e e d = a [ j ] a[i]+k*seed=a[j] a[i]+k∗seed=a[j]，其中 k k k 为任意正整数，移项可得 a [ i ] − a [ j ] ≡ 0 ( m o d s e e d ) a[i]-a[j] \equiv 0 \pmod{seed} a[i]−a[j]≡0(modseed)，到此模型转换为寻找到最小的正整数 m m m，其中不是任意一对 ∣ a [ i ] − a [ j ] ∣ |a[i]-a[j]| ∣a[i]−a[j]∣ 的约数。

直接按照项数枚举的话复杂度是 n 2 n^2 n2 级别的，观察到值域是 [ 0 , 500000 ] [0,500000] [0,500000] 的，即 a [ i ] , a [ j ] ∈ [ 0 , 500000 ] a[i],a[j] \in[0,500000] a[i],a[j]∈[0,500000]，推得 ∣ a [ i ] − a [ j ] ∣ ∈ [ 0 , 500000 ] |a[i]-a[j]|\in[0,500000] ∣a[i]−a[j]∣∈[0,500000]，因为本题中任意两项的值都互不相等，所以可以从值域入手，判断某个值是否存在，此时只需要枚举答案 s e e d seed seed，就可以在 O ( n l o g n ) O(nlogn) O(nlogn) 的时间复杂度内检查答案是否合法。

我们将 a [ i ] = x a[i]=x a[i]=x 转换为 P [ x ] = 1 P[x]=1 P[x]=1，令多项式 { P 0 , P 1 , . . . , P 500000 − 1 , P 500000 } \{ P_{0},P_{1},...,P_{500000-1},P_{500000} \} {P0​,P1​,...,P500000−1​,P500000​} 与 { P 0 , P − 1 , . . . , P − ( 500000 − 1 ) , P − 500000 } \{ P_{0},P_{-1},...,P_{-(500000-1)},P_{-500000} \} {P0​,P−1​,...,P−(500000−1)​,P−500000​} 进行卷积，这样对于其中的 P [ i ] P[i] P[i] 和 P [ j ] P[j] P[j]，卷积后得到 P [ i + j ] P[i+j] P[i+j]，因为 j j j （下标）是负数，所以自然得到了所有的 P i − j P_{i-j} Pi−j​

到此为止就可以用 ntt 或 fft 进行优化了，不过多项式卷积不支持负数，所以需要给会出现负数的位置增加一个偏移量 l i m i t limit limit，令第二个多项式变为： { P l i m i t − 0 , P l i m i t − 1 , . . . , P l i m i t − ( 500000 − 1 ) , P l i m i t − 500000 } \{ P_{limit-0},P_{limit-1},...,P_{limit-(500000-1)},P_{limit-500000} \} {Plimit−0​,Plimit−1​,...,Plimit−(500000−1)​,Plimit−500000​}

因为 ∣ a [ i ] − a [ j ] ∣ ∈ [ 0 , 500000 ] |a[i]-a[j]|\in[0,500000] ∣a[i]−a[j]∣∈[0,500000]，所以最后枚举答案的范围是 [ 1 , 500001 ] [1,500001] [1,500001]

代码：

// Problem: Hash Function
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11166/H
// Memory Limit: 524288 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// #pragma GCC optimize(2)
// #pragma GCC optimize("Ofast","inline","-ffast-math")
// #pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<list>
#include<unordered_map>
#include<complex>
#define cp complex < double >
#define lowbit(x) (x&-x)
using namespace std;
const double pi=acos(-1);
typedef long long LL;
typedef unsigned long long ull;
template<typename T>
inline void read(T &x)
{
	T f=1;x=0;
	char ch=getchar();
	while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	x*=f;
}
template<typename T>
inline void write(T x)
{
	if(x<0){x=~(x-1);putchar('-');}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const int inf=0x3f3f3f3f;
const int N=1e6+100;

int lena=0,lenb=0,n,res[N<<2];
 
cp F[N<<2],G[N<<2],arr[N<<2],inv[N<<2];
 
void init()
{
    for (int i=0;i<n;i++)
    {
        arr[i]=cp(cos(2*pi*i/n),sin(2*pi*i/n));
        inv[i]=conj(arr[i]);
    }
}
void FFT(cp *a,cp *arr)
{
    int lim=0;
    while ((1<<lim)<n) lim++;
    for (int i=0;i<n;i++)
    {
        int t=0;
        for (int j=0;j<lim;j++)
            if ((i>>j) & 1) t|=1<<(lim-j-1);
        if (i<t) swap(a[i],a[t]);
    }
    for (int l=2;l<=n;l*=2)
    {
        int m=l/2;
        for (cp *buf=a;buf!=a+n;buf+=l)
            for (int i=0;i<m;i++)
            {
                cp t=arr[n/l*i]*buf[i+m];
                buf[i+m]=buf[i]-t;
                buf[i]+=t;
            }
    }
}
int main()
{
#ifndef ONLINE_JUDGE
//	freopen("data.in.txt","r",stdin);
//	freopen("data.out.txt","w",stdout);
#endif
//	ios::sync_with_stdio(false);
	lena=lenb=500000;
	read(n);
	for(int i=1;i<=n;i++) {
		int x;
		read(x);
		F[x].real(1);
		G[500000-x].real(1);
	}
	n=1;
    while(n<(lena+lenb))
        n<<=1;
	init();
    FFT(F,arr);FFT(G,arr);
    for(int i=0;i<n;i++)
        F[i]*=G[i];
    FFT(F,inv);
    for(int i=0;i<n;i++)
        res[i]=floor(F[i].real()/n+0.5);
    for(int i=1;i<=500001;i++) {
    	bool flag=true;
    	for(int j=500000+i;j<=1000000;j+=i) {
    		if(res[j]) {
    			flag=false;
    			break;
    		}
    	}
    	if(flag) {
    		return 0*printf("%d\n",i);
    	}
    }
	return 0;
}