题解 | #Hash Function#

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

Describe

给定 $n+m$ 个数： $A = \{a_1,a_2,a_3,a_4,a_5.......a_n\} \\ B = \{b_1,b_2,b_3,b_4,b_5.......b_m\}$
求 $A \pm B$ 的集合 $C$

注意： $A+B$ 指的是 $A$ 中的每一个元素与 $B$ 中的每一个元素相加，即 $C = \{c_{ij}\ |\ \forall i \in [1,n],\forall j \in [1,m] \}$

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

Solve

朴素双重循环复杂度为 $O(N^2)$ ，对于数据量大于 $10^5$ 的问题显然无法解决。

考虑 $\forall a_n,|a_n| \le 10^5 ;\ \forall b_n,|b_n| \le 10^5$ 我们将上述集合换一种表达式： $A(x) = x^{a_1} + x^{a_2} + x^{a_3} ...... x^{a_n} \\ B(x) = x^{b_1} + x^{b_2} + x^{b_3} ...... x^{b_m}$
则对于 $C = A + B$ ，转化为 $C(x) = A(x) * B(x)$
$C(x) = A(x)*B(x) =\sum _{\forall (i,j) \in [1,1] \times [n,m]} x^{a_i + b_j}$
因此，我们只要将一个多项式中的 $x^{a_n} 和 x^{b_m}$ 的系数赋值为 $1$ ，其他赋值为 $0$ 。进行一遍FFT后，检验 $x^k$ 的系数，若 $x^k$ 的系数大于等于 $1$ ，则 $k \in C$ 。

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

具体问题讲解

题面描述 [Hash Function]

给定一个集合 $A = \{a_1,a_2,a_3...a_n\} ;\ n \le 5 \times 10^5 ;\ \forall a_i \in A, 0\le a_i \le 5 \times 10^ 5$
考虑 $hash(a_i) = a_i \% Seed$ ，求最小的整数 $Seed$ ，使得 $hash(a_i)$ 无冲突，即若 $a_i,a_j \in A ;a_i \neq a_j$ ，则 $hase(a_i) \neq hash(a_j)$ 。

Slove

我们需要考虑的是 $\forall i,j \in [1,n]； a_i \% Seed \neq a_j \% Seed$ ，都存在 $|a_i - a_j| \% Seed \neq 0$ .

上述结论很容易证明：

考虑： $a_i \le a_j$ ，则 $a_i = a_i \\ a_j = a_i + a_j - a_i = a_i + |a_j - a_i|$
显然 $a_i \ \% \ Seed = a_i \ \% \ Seed \\ a_j \ \% \ Seed = a_i \ \% \ Seed + |a_j - a_i| \ \% \ Seed$
如果 $|a_j - a_i| \ \% \ Seed = 0$ ，则 $a_i \% Seed = a_j \% Seed$ 。则 $Seed$ 不合法。

也就是说 $\forall i,j \in [1,n]$ ， $|a_i - a_j|$ 的因子全都不满足条件，同时对于其他数，一定都是满足条件的，证明如下：

因为 $|a_i - a_j| \ \% \ Seed \neq 0$ ；且 $|a_i - a_j| \ \% \ Seed < Seed$ ；则 $(a_i \ \% \ Seed + |a_i - a_j| \ \% \ Seed) \ \% \ Seed \neq a_i \ \% \ Seed$
说明 $a_i \ \% \ Seed \ \neq a_j \ \% \ Seed$ ，同时对于每一对 $(i,j)$ 都成立，故该 $Seed$ 合法。

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

即我们需要求出 $C = \{ \forall (i,j) \in [n \times n] \ | \ |a_i - a_j|\}$
上述做法即可在 $O(NlogN)$ 内完成，根据经验， $C$ 中元素不超过 $2N$ 个，同时元素不超过 $5 \times 10^5$ ，用正向筛选法可以在 $O(NlogN)$ 内筛选出所有因子。

代码：

#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;
}