Problem

Given the array and find the smallest p such that each number is different after modulo p.

Solution

  • a % p = b % p is equivalent to (a-b)%p = 0 ,

so we only need to know all the ∣ai−aj∣\left| a_{i}-a_{j} \right| then we can enumerate the multiples to find the smallest p.
To find all the differences we can use FTT ,
which can be transformed into

(xa1+xa2+xa3+......+xan)∗(x−a1+x−a2+x−a3+...+x−an)(x^{a_{1}}+x^{a_{2}}+x^{a_{3}}+......+x^{a_{n}})*(x^{-a_{1}}+x^{-a_{2}}+x^{-a_{3}}+...+x^{-a_{n}})

The exponent of the coefficient greater than 0 is the difference that exists

  • Consider A as a polynomial whose coefficient is 1 if aia_{i} exists and 0 otherwise
  • The two polynomials A, B, which can be regarded as an infinite sequence, are convolved to give the infinite polynomial C. An offset needs to be added here to ensure that all the terms of the polynomial are positive integers to the power of the term (Because C++ arrays do not allow negative subscripts).
  • At this point the existence of the difference is indicated by whether the coefficient ofcic_{i} is equal to 0 or not.
    The smallest positive integer that is not marked is the answer.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    #include <algorithm>
    #include <iostream>
    #include <cstring>
    #define ull unsigned long long
    using namespace std;
    #define fast ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    const int P = 998244353;
    const int L = 20;
    int norm(int x) { return x >= P ? x - P : x; }
    int reduce(int x) { return x < 0 ? x + P : x; }
    int neg(int x) { return x ? P - x : 0; }
    void add(int &x, int y) {
        if ((x += y - P) < 0) x += P;
    }
    void sub(int &x, int y) {
        if ((x -= y) < 0) x += P;
    }
    void fam(int &x, int y, int z) { x = (x + y * (ull) z) % P; }

    int mpow(int x, unsigned k) {
        if (k == 0) return 1;
        int res = mpow(x * (ull) x % P, k >> 1);
        if (k & 1) res = res * (ull) x % P;
        return res;
    }

    namespace NTT {
        const int o = 31;
        int l, n;
        int w2[(1 << L) + 1];

        void init(){
            n = 1 << l;
            *w2 = 1;
            w2[1 << l] = mpow(o, 1<< (21 - l));
            for (int i = l; i; --i)
                w2[1 << (i - 1)] = w2[1 << i] * (ull)w2[1 << i] % P;
            for (int i = 1; i < n; ++i)
                w2[i] = w2[i & (i - 1)]*(ull)w2[i & -i] % P;
        }

        void DIF (int *a){
            int i, *j, *k, len = n >> 1, r, *o;
            for (i = 0; i < l; ++i, len >>= 1)
                for (j = a,o = w2; j != a + n; j += len << 1, ++o)
                    for (k = j;k != j + len; ++k)
                        r = *o*(ull)k[len] % P, k[len] = reduce(*k - r), add(*k, r);
        }

        void DIT(int* a){
            int i, *j, *k, len = 1, r,*o;
            for (i = 0; i < l; ++i, len <<=1)
                for (j = a,o = w2; j != a + n; j += len << 1, ++o)
                    for (k = j; k != j + len; ++k)
                        r = reduce(*k + k[len] - P), k[len] = (ull)(*k - k[len] + P)* *o % P, *k = r;
        }

        void FFT(int *a, int d = 1) {
            if (d == 1) DIF(a);
            else {
                DIT(a);
                reverse(a + 1, a + n);
                ull nv = P - (P - 1) / n;
                for (int i = 0; i < n; i++)
                    a[i] = a[i] * nv % P;
            }
        }
    }
    using NTT::l;
    int n,m;
    int a[1 << L], b[1 << L];

    int main(){
        fast
        cin >> n;
        int tmp;
        while (n--) {
            cin >> tmp;
            a[tmp] = 1;
            m = max(m, tmp);
        }
        ++m;
        while ((1 << l) <= m * 2)
            ++l;
        NTT::init();
        memcpy(b,a,sizeof(a));
        reverse(b + 1, b + (1 << l));
        NTT::FFT(a);
        NTT::FFT(b);
        for (int i = 0; i != 1 << l; ++i)
            a[i] = a[i] * (ull)b[i] % P;
        NTT::FFT(a,-1);
        for (int i = 1; i <= m; ++i) {
            bool fl = false;
            for (int j = i; j <=m; j += i) fl |= a[j];
            if (!fl){
                cout << i << "\n";
                break;
            }
        }
        return 0;
    }