题目大意
有 $n$ 个数 $a_1, a_2, \cdots, a_n$。要选出一个子集，使得集合内部的 $\gcd$ 为 $1$，问集合大小的最小值。
数据范围：$n, a_i \le 3 \times 10^5$。
思路分析
这题看似是个神仙题，实际上是个脑筋急转弯题。
由于 $2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 > 3 \times 10^5$，所以答案一定不超过 $7$。
这样，我们就可以令 $\text{dp}(i, j)$ 表示集合大小为 $i$，$\gcd$ 为 $j$ 的方案数。转移时我们只需要枚举每个数的倍数的复杂度，可以证明这是 $O(n \log n)$ 的，所以总共的复杂度也是 $O(n \log n)$ 的。
代码实现
1 | |
2 | using namespace std; |
3 | |
4 | typedef long long ll; |
5 | const int maxn = 3e5, mod = 1926081733; |
6 | int n, m, d, a[maxn + 3], b[maxn + 3]; |
7 | |
8 | int gcd(int a, int b) { |
9 | return b ? gcd(b, a % b) : a; |
10 | } |
11 | |
12 | int main() { |
13 | scanf("%d", &n); |
14 | for (int i = 1, x; i <= n; i++) { |
15 | scanf("%d", &x); |
16 | a[x] = b[x] = 1; |
17 | m = max(m, x); |
18 | d = gcd(d, x); |
19 | } |
20 | if (d > 1) { |
21 | puts("-1"); |
22 | return 0; |
23 | } |
24 | for (int i = 1; i <= m; i++) { |
25 | for (int j = i * 2; j <= m; j += i) { |
26 | a[i] += a[j]; |
27 | } |
28 | } |
29 | for (int _ = 1; ; _++) { |
30 | if (b[1]) { |
31 | printf("%d\n", _); |
32 | break; |
33 | } |
34 | for (int i = 1, x; i <= m; i++) { |
35 | ll sum = 0; |
36 | for (int j = i; j <= m; j += i) { |
37 | sum += b[j]; |
38 | } |
39 | x = sum % mod; |
40 | b[i] = 1ll * a[i] * x % mod; |
41 | } |
42 | for (int i = m; i; i--) { |
43 | ll x = 1ll * mod * mod + b[i]; |
44 | for (int j = i * 2; j <= m; j += i) { |
45 | x -= b[j]; |
46 | } |
47 | b[i] = x % mod; |
48 | } |
49 | } |
50 | return 0; |
51 | } |