题解 | #Hash Function#

H - Hash Function

题意： 给出 $n(n \leq 500000)$ 个互不相同的数，找一个最小的模数，使得这些数字对这个模数取模的结果互不相同。

题解：

$a[i]$ % $m \ != a[j]$ % $m$ 转化为 $|a[i] - a[j]|$ % $m \ != 0$
问题就转化为找一个 $m$ ,他不是任意一个 $|a[i] - a[j]|$ 的约数
问题就来到了如何快速求一个数列中每两个数之间的差，如果暴力是 $O(n^2)$ 会超时
我们考虑多项式乘法，用指数的减代表两个数直接的差，因为在 $fft$ 中指数不能为负，所以我们将指数整体加 $500000$
做完 $fft$ 后就是枚举 $m$ ,直到他不是某个 $|a[j] - a[i]|$ 的约数为止，如果找不到则为 $500001$
特判 $n = 1$ 的情况

#include<bits/stdc++.h>
using namespace std;

#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {   cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...);}

inline int rd() {
    int f = 0; int x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}

void out(int a) {if(a<0)putchar('-'),a=-a;if(a>=10)out(a/10);putchar(a%10+'0');}
#define pt(x) out(x),puts("")
#define ll long long
#define ull unsigned long long
#define LL __int128
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define PII pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define PAUSE system("pause");
const double Pi = acos(-1.0);
const double eps = 1e-8;
const int maxn = 5e6 + 10;
const int maxm = 6e2 + 10;
const int mod = 999911659;
const int P = 131;

inline void swap(ll &a, ll &b){ll t = a; a = b; b = t;}
inline ll min(ll a, ll b){return a < b ? a : b;}
inline ll max(ll a, ll b){return a > b ? a : b;}
// const int mod = 998244353;
struct Complex{
    double x,y;
    Complex (double xx=0,double yy=0){x=xx,y=yy;}
}a[maxn],b[maxn];
Complex operator + (Complex a,Complex b){ return Complex(a.x+b.x , a.y+b.y);}
Complex operator - (Complex a,Complex b){ return Complex(a.x-b.x , a.y-b.y);}
Complex operator * (Complex a,Complex b){ return Complex(a.x*b.x-a.y*b.y , a.x*b.y+a.y*b.x);}
ll l,r[maxn];
ll limit=1;
void fast_fast_tle(Complex *A, int type){
    for(int i = 0; i < limit; i++) 
        if(i < r[i]) swap(A[i], A[r[i]]);
    for(int mid = 1; mid < limit; mid <<= 1){
        Complex Wn(cos(Pi/mid), type*sin(Pi / mid));
        for(int R = mid << 1, j = 0; j < limit; j += R){
            Complex w(1, 0);
            for(int k = 0; k < mid; k++, w = w * Wn){
                Complex x = A[j + k], y = w * A[j + mid + k];
                A[j + k] = x + y;
                A[j + mid + k] = x - y;
            }
        }
    }
}
ll n, c[maxn];

void solve(){
    n = rd();
    for(int i = 1; i <= n; i++) {
        int x = rd();
        a[x + 500000] = 1;
        b[500000 - x] = 1;
    }
    if(n == 1) {
        puts("1");
        return ;
    }
    while(limit <= 1500000) limit <<= 1, l++;
    for(int i = 0; i < limit; i++)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    fast_fast_tle(a, 1);
    fast_fast_tle(b, 1);
    for(int i = 0; i <= limit; i++) a[i] = a[i] * b[i];
    fast_fast_tle(a, -1);
    int minn = inf;
    for(int i = 1000001, j = 999999; i <= 1500000, j >= 500000; i++, j--) {
        c[i - 1000000] = (int)(a[i].x/limit+0.5) + (int)(a[j].x/limit + 0.5);
    }
    for(int i = 2; i <= 500000; i++) {
        bool flag = true;
        for(int j = i; j <= 500000; j += i) {
            if(c[j]) {
                flag = false;
                break;
            }
        }
        if(flag) {
            printf("%d\n", i);
            return ;
        }
    }
    puts("500001");
}

int main() {
    // freopen("02.in","r",stdin);
    int t = 1;
    // t = rd();
    while(t--)
        solve();
    return 0;
}