Hash Function

2021-07-28

字数统计: 1.3k字 | 阅读时长≈ 5分

Hash Function

题目大意

给出n个不同的自然数$a_1,a_2,...a_n$，求出最小的自然数m，使 \[ a_1\mod{m},\quad a_2\mod{m},...,\quad a_n\mod{m}, \] 依然互不相等。 ( $n $ )

原题链接

思路

我们可以发现 $a_i \mod{m} \enspace \not = \enspace a_j \mod {m}$ 的充分必要条件是$|a_i - a_j| \mod {m}\enspace \not = \enspace 0$

可以证明：

不妨假设 $a_j \le a_i$

显然有： $a_j = a_i + a_j - a_i$

可以化为： $a_j = a_i + |a_j - a_i|$

那么$a_j \mod{m}$ 等价于 $a_i\mod{m} \enspace +\enspace |a_j - a_i| \mod{m}$

所以，只要 $|a_j - a_i| \mod{m} \not = 0$ ，那么 $a_i \mod{m} \not = a_j \mod {m}$

以上证明逐步可逆
所以我们的任务就变为了求出所有的$|a_i - a_j|$ ,那么如何求出它呢？这时，我们就可以利用离散卷积。

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

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

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

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

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

前文说到，$y(n)$的值是序列$f, g$的所有 自变量之和为n时,它们的函数值的乘积 之和

那么我们分别把a, b两个数组转换为pa, pb数组,对它们进行卷积，得到了数组P

那么我们想一下数组P的每一个数是怎么求出来了，对于$P_i$,它的值为 $\sum pa_x * pa_y$ 其中，$x + y = i$ ,而$pa_x, pa_y$的值只有0，1两中情况，那么 只有至少有一组$pa_x, pb_y$均为1时,$P_i$的值才不为0。

所以，卷积得到的P数组，其实就是我们需要的结果，只需检查一下P数组的每一个，只要当前下标下的值大于0，那么就意味着这个数存在于新的数组。

那么回到我们现在的问题，我们知道了加法，那么我们如何解决当前这个问题呢？

其实很简单，我们把数组原来的所有数组取相反数，再映射到新的p数组，得到p‘（当然此时的p’数组下标均为负数），那么我们只需要把p和p‘进行卷积，得到的P数组，就是我们要的结果了。

当然因为C++中不能使用负数作为下标，所以我们要做数组平移，即把下标 -x 改为 Max - x，就可以了。
如果我们按照定义的方法去求卷积，其复杂度为$O(n^2)$,是和暴力算法复杂度一样。~~一直以来的努力全部木大~~，但是，离散卷积，刚好就是快速傅里叶变换（FFT）解决多项式相乘问题中的一步。所以我们可以使用FFT来优化离散卷积过程，把时间复杂度降为$O(nlogn)$。

题外话

一个n阶多项式系数数组经过FFT后得到的数组F，$F_i$就是$i$阶单位根为自变量的值时，多项式的值。
得到了所有的$|a_i - a_j|$数组，我们只需要找一个不被它们整除的数即可，时间复杂度$O(nlogn)$。

代码

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

本文作者： 水蓝络合物
本文链接： https://miku39393939.github.io/2021/07/28/HashFunction/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！