Hash Function（fft）

链接：H-Hash Function_2024牛客五一集训派对day4 (nowcoder.com)

题意：给定一个序列，求使得任意两数的hash值不同的最小模数；

分析：a=b(mod seed)

|a-b|%seed=0;

也就是说seed不能是任意两数差的因子。

如果暴力求解，o（n2），会超时，可以用fft来优化。

序列为当以a1>0时，我们就让 $x^{a1}$ 的系数为1；

对于另一个序列，本应该是 $x^{-a1}$ ,但次方不可<0，所以让所有次方加上500000，让 $x^{50000-a1}$ 系数为1。

让两序列进行fft，得到序列如果 $x^{a}$ 系数大于0,说明存在a=ai-aj+50000这样的数存在，让a-50000，存到一个数组中。

然后从n枚举到500000，枚举n的倍数，如果数组中没有n的倍数，答案就取n；

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=3e6;
const long long inf=1e9;
const long long mod=998244353;
const double PI=acos(-1);
int n;
int ans[N];
typedef struct Complex
{
   double x;
   double y;
   Complex operator +(const Complex &a)const
   {
       return {x+a.x,y+a.y};
   }
   Complex operator -(const Complex &a) const
   {
       return {x-a.x,y-a.y};
   }
   Complex operator *(const Complex &a)const
   {
       return {x*a.x-y*a.y,x*a.y+y*a.x};
   }


};
Complex a[N],b[N];
int c[N],tot,bit,rel[N];
void change(Complex a[])
{
   for(int i=0;i<tot;i++)
   if(i<rel[i]) swap(a[i],a[rel[i]]);
}
void fft(Complex a[],int op)
{
change(a);
for(int m=2;m<=tot;m<<=1)
{
    Complex w1({cos(2*PI/m),op*sin(2*PI/m)});
    for(int i=0;i<tot;i+=m)
    { Complex wk({1,0});
        for(int j=0;j<m/2;j++)
        {
           Complex x=a[i+j],y=a[i+j+m/2]*wk;
           a[i+j]=x+y;
           a[i+j+m/2]=x-y;
           wk=wk*w1;
           }
       }
}
}
int main()
{ cin>>n;
for(int i=1;i<=n;i++)
{ scanf("%d",&c[i]);
a[c[i]].x=1;
   b[500000-c[i]].x=1;
   }
while((1<<(bit))<2*500001+1) bit++;
tot=1<<(bit);
for(int i=0;i<tot;i++) rel[i]=rel[i/2]/2+((i&1)? tot/2:0);
fft(a,1);
fft(b,1);
for(int i=0;i<tot;i++) a[i]=a[i]*b[i];
fft(a,-1);
for(int i=0;i<tot;i++)
{
if(int(a[i].x/tot+0.5)>0)
   ans[abs(500000-i)]=1;
   }
   int x=1;
   for(x=n;;x++)
   {
   int flag=1;
       for(int j=x;j<=500000;j+=x)
       if(ans[j])
       { flag=0;
       break;
       }
       if(flag) break;
   }
   cout<<x<<endl;
    return 0;
}