2021牛客暑期多校训练营1 H

H. Hash Function

题目描述

For a given set $S = \{a_0, a_1, a_2, ..., a_{n-1}\}$ , we called a hash function $f_S(x)$ perfect hash function of $S$ , if it satisfies $\forall 0 \leq i < j < n$ , $f_S(a_i) \neq f_S(a_j)$ .

Given a set S with non-negative integers, please find the minimum positive integer seed that function $h_{seed}(x) = x \bmod seed$ is a perfect hash function of $S$ .

输入描述

The first line of input contains one integer $n$ , describing the size of set $S$ .

The second line contains $n$ ( $1 \leq n \le 500000$ ) integers $a_0,...,a_{n-1}$ , describing the elements in $S$ .

It is guaranteed that $\forall 0 \leq i < j < n,$ $a_i \ne a_j$ , $0 \le a_i \le 500000$ .

输出描述

Output one integer in a line, indicating the answer.

示例1

输入

3
2 3 4

输出

示例2

输入

3
1 2 4

输出

示例3

输入

10
0 7 23 18 29 27 6 28 24 11

输出

思路

$\forall0\le i<j<n$ ， $a_i\not\equiv a_j\pmod s$ ；等价于 $\forall0\le i<j<n$ ， $s\not\mid(a_i-a_j)$ 。注意到数据范围较小，集合中任意两数的差属于 $(-500000,500000)$ ，可进行多项式优化，用 NTT 或 FTT 得到某个差值是否存在。

定义两个多项式 $A,B$ ，系数分别为 $a_i,b_i$ ；两者的卷积为 $C$ ， $c_k=\sum\limits_{i+j=k}a_ib_j$ 。我们的想法是令 $c_k$ 为差值 $k$ 是否存在的标志，那么卷积 $\sum$ 的限制条件应该为 $i-j=k$ ，但是下标不可能为负数，因此我们需要将 $B$ 的系数下标增加一个偏移量 $M=500000$ 。若 $i\in S$ ，则 $a_i=1$ ， $b_{M-i}=1$ 。两个多项式进行卷积运算，就能得到差值是否存在的信息， $c_k=\sum\limits_{i+M-j=k}a_ib_{M-j}$ ；若 $c_k>0$ ，就代表 $k-M$ 的差值存在。

我们枚举最终的答案 $s$ ，根据抽屉原理， $s$ 可以直接从 $n$ 开始枚举。对于当前的模数 $s$ ，我们需要快速查询存在的差值中是否有一个差值 $s|\delta$ ；我们只需要枚举 $s$ 的所有倍数，检查是否存在 $s$ 的某个倍数正好是 $S$ 中两数的差。枚举的时间复杂度是 $O(N\log N)$ 。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2021牛客多校训练营1 H
Date: 2021 July 24th
Description: NTT, Number Theory
*******************************************************************/
#include<iostream>
using namespace std;
typedef long long ll;
const int SIZE = 1 << 21;
const int MAX = 500000;
const int MOD = 998244353;
int n;
ll a[SIZE], b[SIZE], res[SIZE], rev[SIZE];
int len = 1 << 20;
ll quickPow(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
        {
            res = res * a % MOD;
        }
        b >>= 1;
        a = a * a % MOD;
    }
    return res;
}
void NTT(ll* a, short opt)
{
    for (int i = 0; i < len; i++)
    {
        if (i < rev[i])
        {
            swap(a[i], a[rev[i]]);
        }
    }
    for (int k = 2; k <= len; k <<= 1)
    {
        ll m = k >> 1, x = quickPow(3, (MOD - 1) / k), w = 1, v;
        if (opt == -1)
        {
            x = quickPow(x, MOD - 2);
        }
        for (int i = 0; i < len; i += k, w = 1)
        {
            for (int j = i; j < i + m; j++)
            {
                v = w * a[j + m] % MOD;
                a[j + m] = (a[j] - v + MOD) % MOD;
                a[j] = (a[j] + v) % MOD;
                w = w * x % MOD;
            }
        }
    }
    if (opt == -1)
    {
        ll inv = quickPow(len, MOD - 2);
        for (int i = 0; i < len; i++)
        {
            a[i] = a[i] * inv % MOD;
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        a[x] = 1;
        b[MAX - x] = 1;
    }
    for (int i = 0; i < len; i++)
    {
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? len >> 1 : 0);
    }
    NTT(a, 1);
    NTT(b, 1);
    for (int i = 0; i < len; i++)
    {
        res[i] = a[i] * b[i] % MOD;
    }
    NTT(res, -1);
    // 所有差是否存在都已经知道
    for (int ans = n;; ++ans)
    {
        bool ok = true;
        for (int p = ans; p <= MAX; p += ans)
        {
            if (res[p + MAX])
            {
                ok = false;
                break;
            }

        }
        // 没必要枚举负数差值，因为两数的两个差互为相反数。
        // for (int p = -ans; p >= -MAX; p -= ans)
        // {
        //     if (res[p + MAX])
        //     {
        //         ok = false;
        //         break;
        //     }
        // }
        if (ok)
        {
            cout << ans << endl;
            return 0;
        }
    }
}