Hash Function题解

题目大意

给出 $n$ 个不同的自然数 $a_1, a_2, \ldots, a_n$，求最小的正整数 $m$，使得 $a_1 \bmod m,\ a_2 \bmod m,\ \ldots,\ a_n \bmod m$ 依然互不相等。（$n \le 500000$）

原题链接

思路

1. 我们可以发现，$a_i \bmod m \ne a_j \bmod m$ 的充分必要条件是 $|a_i - a_j| \bmod m \ne 0$。

   可以证明：

   不妨假设 $a_j \le a_i$，显然有 $a_j = a_i + a_j - a_i$，可以化为 $a_j = a_i + |a_j - a_i|$。

   那么 $a_j \bmod m$ 等价于 $(a_i \bmod m) + (|a_j - a_i| \bmod m)$。

   所以，只要 $|a_j - a_i| \bmod m \ne 0$，那么 $a_i \bmod m \ne a_j \bmod m$。

   以上证明逐步可逆。

2. 所以我们的任务就变为了求出所有的 $|a_i - a_j|$，再找最小的 $m$ 使得每个 $|a_i - a_j|$ 都不是 $m$ 的倍数。

   考虑一下卷积的计算过程，假如有序列 $f(n), g(n)$，则其卷积为：

   $$y(n) = \sum_{i=-\infty}^{\infty} x(i) \cdot h(n-i)$$

   可以看出，$y(n)$ 的值是序列 $f, g$ 的所有自变量之和为 $n$ 时，它们的函数值的乘积之和。

   如果我们把给出的自然数映射到新的数组 $p$，$p_i = 1$ 表示 $i$ 存在，$p_i = 0$ 表示 $i$ 不存在。

   我们先来考虑一个类似的问题：假如给定了 $a, b$ 两个自然数数组，怎么知道两个数组中任意两个数相加后所得到的新数组中都有哪些数呢？

   分别把 $a, b$ 两个数组转换为 $p_a, p_b$ 数组，对它们进行卷积，得到数组 $P$。

   对于 $P_i$，它的值为 $\sum p_{a_x} \cdot p_{b_y}$，其中 $x + y = i$。由于 $p_{a_x}, p_{b_y}$ 的值只有0、1两种情况，所以只有至少有一组 $p_{a_x}, p_{b_y}$ 均为1时，$P_i$ 的值才不为0。

   所以卷积得到的 $P$ 数组，只需检查每个位置的值，大于0则意味着这个数存在于新的数组。

   那么回到我们现在的问题：把数组中所有数取相反数，再映射到新的 $p’$ 数组（下标均为负数），把 $p$ 和 $p’$ 进行卷积，得到的 $P$ 数组就是所有差值组成的数组。

   因为C++中不能使用负数作为下标，所以要做数组平移，把下标 $-x$ 改为 $Max - x$。

3. 如果按照定义的方法求卷积，其复杂度为 $O(n^2)$，和暴力算法复杂度一样。一直以来的努力全部木大，但是，离散卷积刚好就是快速傅里叶变换（FFT）解决多项式相乘问题中的一步，可以把时间复杂度降为 $O(n \log n)$。

4. 得到了所有的 $|a_i - a_j|$ 之后，从小到大枚举 $m$，检查每个 $|a_i - a_j|$ 是否都不是 $m$ 的倍数，总复杂度 $O(n \log n)$。

代码

#include <cstdio>
#include <iostream>
#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 << 1], b[lim << 1];

bool vis[lim << 1];

void FFT(CP* x, int lim, int inv)
{
    int bit = 1, m;
    CP stand, now, tmp;
    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 = now * stand) {
                tmp = now * p[i + m];
                p[i + m] = p[i] - tmp;
                p[i] = p[i] + tmp;
            }
        }
    }

    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 false;
    }
    return true;
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        int x;
        scanf("%d", &x);
        a[x] = CP(1, 0);
        b[P - x] = CP(1, 0);
    }
    int num = 1 << 20;
    FFT(a, num, 1);
    FFT(b, num, 1);
    for(int i = 0; i < lim; ++i)
        a[i] = a[i] * b[i];
    FFT(a, num, -1);
    for(int i = 0; i < lim; ++i) {
        int 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;
}