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
| #include <iostream>
#include <algorithm>
#include <cstring>
#define maxn 2100010
#define ll long long
#define offset 500000
using namespace std;
const int N = 500000;
const int p = 998244353;
const int G = 3;
const int Gi = 332748118;
ll pow_mod(ll x, ll n) {
ll s = 1;
for (; n; n >>= 1, x = x * x % p)
if (n & 1) s = s * x % p;
return s;
}
int n;
int vis[maxn];
ll A[maxn], B[maxn];
ll a[maxn], b[maxn];
int P[maxn];
void init_P(int n) {
int l = 0; while ((1 << l) < n) ++l;
for (int i = 0; i < n; ++i) P[i] = (P[i >> 1] >> 1) | ((i & 1) << l - 1);
}
void NTT(ll *a, int n, int type) {
for (int i = 0; i < n; ++i) if (i < P[i]) swap(a[i], a[P[i]]);
for (int i = 2, m = 1; i <= n; m = i, i *= 2)
for (int j = 0; j < n; j += i) {
ll wn = pow_mod(type > 0 ? G : Gi, (p - 1) / i), w = 1;
for (int k = 0; k < m; ++k, w = w * wn % p) {
ll t1 = a[j + k], t2 = a[j + k + m] * w % p;
a[j + k] = (t1 + t2) % p; a[j + k + m] = (t1 - t2) % p;
}
}
if (type < 0) {
ll inv = pow_mod(n, p - 2);
for (int i = 0; i < n; ++i) a[i] = a[i] * inv % p;
}
}
void Mul(ll *a, ll *B, int n1, int n2) {
int n = 1; while (n < n1 + n2 - 1) n <<= 1; init_P(n);
for (int i = 0; i < n2; ++i) b[i] = B[i];
fill(a + n1, a + n, 0); fill(b + n2, b + n, 0);
NTT(a, n, 1); NTT(b, n, 1);
for (int i = 0; i < n; ++i) a[i] = a[i] * b[i];
NTT(a, n, -1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 1, x; i <= n; ++i) cin >> x, A[x] = B[-x + offset] = 1;
Mul(A, B, 2 * N, 2 * N);
for (int i = N + 1; i <= 2 * N; ++i)
if (A[i]) vis[i - N] = 1;
for (int i = 1; i <= N; ++i) {
bool ok = 1;
for (int j = i; j <= N; j += i)
if (vis[j]) ok = 0;
if (ok) return cout << i << "\n", 0;
} cout << N + 1 << "\n";
return 0;
}
|