题解 | #Hash Function#

个数两个相减（相加）先序知识

Describe

给定 个数 ：
求 的集合

注意： 指的是 中的每一个元素与 中的每一个元素相加，即

相关题型：Hash Function B-小圆前辈的素数

Solve

朴素双重循环复杂度为 ，对于数据量大于 的问题显然无法解决。

考虑 我们将上述集合换一种表达式：
则对于 ，转化为

因此，我们只要将一个多项式中的 的系数赋值为 ，其他赋值为 。进行一遍FFT后，检验 的系数，若 的系数大于等于 ，则 。

提示：对于减法，实际上是加上一个负数，因为负下标的问题，可以先统一加上一个偏移量，最后减去即可得到原值。

具体问题讲解

题面描述 [Hash Function]

给定一个集合
考虑 ，求最小的整数 ，使得 无冲突，即若 ，则 。

Slove

我们需要考虑的是 ，都存在 .

上述结论很容易证明：

考虑： ，则
显然
如果 ，则 。则 不合法。

也就是说 ， 的因子全都不满足条件，同时对于其他数，一定都是满足条件的，证明如下：

因为 ；且 ；则
说明 ，同时对于每一对 都成立，故该 合法。

综上所述：我们需要快速求出所有的 ，并求出 的所有因子。

即我们需要求出
上述做法即可在 内完成，根据经验，中元素不超过个，同时元素不超过 ，用正向筛选法可以在内筛选出所有因子。

代码：

#include <cstdio>
#include <complex>
#include <cmath>
using namespace std;

int n,m;
typedef complex<double> CP;
const int lim = 1<<21;
const double Pi = acos(-1);
const int P = 500001;
CP a[lim],b[lim];
bool vis[lim];

void FFT(CP *x,int lim,int inv) // 板子而已
{
   int bit = 1,m;
   CP stand,now,temp;
   while((1<<bit) < lim) ++bit;
   for (int i = 0; i < lim; ++i)
   {
       m = 0;
       for (int j = 0; j < bit; ++j)
           if(i & (1<<j)) m |= (1<<(bit-j-1));
       if(i < m) swap(x[m],x[i]);
   }
   for (int len = 2; len <= lim; len <<= 1)
   {
       m = len >> 1;
       stand = CP(cos(2*Pi/len),inv*sin(2*Pi/len));
       for (CP *p = x; p != x+lim; p += len)
       {
           now = CP(1,0);
           for (int i = 0; i < m; ++i,now*=stand)
           {
               temp = now * p[i+m];
               p[i+m] = p[i] - temp;
               p[i] = p[i] + temp;
           }
       }
   }
   if(inv == -1) 
       for (int i = 0; i < lim; ++i)
           x[i].real(x[i].real()/lim);
}

bool check(int x)
{
   for (int i = x; i <= P; i += x)
   {
       if (vis[i] == 1) return 0;
   }
   return 1;
}

int main()
{
   int x;
   scanf("%d",&n);
   for (int i = 0; i < n; ++i)
   {
       scanf("%d",&x);
       a[x].real(1);
       b[P - x].real(1); // 负数做偏移
   }
   int num = 1 << 20;
   FFT(a,num,1);
   FFT(b,num,1);
   for (int i = 0; i < num; ++i)
       a[i] *= b[i];
   FFT(a,num,-1);
   for (int i = 0; i <= num; ++i)
   {
       x = (int)floor(a[i].real()+0.5);
       if (x > 0) vis[abs(i - P)] = 1;
   }
   for (int  i = n; i < P+1; ++i)
       if (check(i))
       {
           printf ("%d\n",i);
           break;
       }
   return 0;
}