CF2115A - Gellyfish and Flaming Peony
chenmingeng
·
·
题解
Description
给定一个包含 N 个正整数的数组 A。任意次操作：选择两个索引 n 和 m，然后将 A_n 的值更新为 \gcd(A_n, A_m)。求出让数组中所有元素都相等所需的最少操作次数。
官方题解给出了本题的 Bonus 版本：Try to solve n, a_i \leq 2 \times 10^5 with only one test case. 设值域为 V，期望复杂度 \mathcal{O}(V\log V)。
所有元素最终必然会相等，且等于整个初始数组的 GCD。问题的核心就变成了如何求得最小的 GCD。
Notes
Step 1 迭代求解
考虑到求得最小的 GCD 需要的数不会很多，事实上最大只会是 \omega(V)=8，即 V 以内一个数的最大素因子个数。
我们采用迭代的方式求解。迭代 t 轮次后得到：恰好选出 t 个数（允许重复），它们的 GCD 可能为哪些。循环 \omega(V) 轮次后就找出答案，每轮迭代期望复杂度 \mathcal{O}(V\log V)。
设
-
-
每一轮迭代需要用 $f$ 来更新 $g_{t}$，具体来说是 $g_{t}[i]$ 将被赋值为：是否有可能从 $f$ 中选一个数 $x$，再从 $g_{t - 1}$ 选一个数 $y$，且其最大公约数 $\gcd(x, y)=i$。
总的复杂度 $\mathcal{O}(V\log^{3} V\omega(V))$，跑 2e5 的数据还是有点危险的。
---
### Step 2 辅助数组与反演
进一步优化，引入辅助数组
- $G_{t}[i]$ 表示：是否有可能从 $f$ 中选一个数 $x$，再从 $g_{t - 1}$ 选一个数 $y$，它们的最大公约数 $\gcd(x, y)$ 是 $i$ 的倍数。
这样 $x$ 和 $y$ 都一定是 $i$ 的倍数，通过枚举倍数在 $\mathcal{O}(V\log V)$ 的时间就能求出 $h$ 数组。
显然 $\displaystyle G_{t}[n]=\sum_{k} g_{t}[nk]$，为了反过来，用 $G_{t}$ 表示 $g_{t}$，就需要用到反演。
Zeta - Möbius Transform 用于计算偏序集上一个元素的所有上级（或下级）元素的某个函数值的总和。在这里我们将其应用到「倍数——因子」这个上下级关系，即
$$
\begin{aligned}
\displaystyle x[n] &= \sum_{d = 1}^ {\infty} \mu[d] \cdot X[n d]
\\
\displaystyle X[n] &= \sum_{d = 1}^ {\infty} x[n d]
\end{aligned}
$$
因此得到
$$
\displaystyle g_{t}[n] = \sum_{k}\mu[k] \cdot G_{t}[n k]
$$
其中 $d \mid n$ 表示 $d$ 是 $n$ 的约数，莫比乌斯函数 $\mu[n] = \begin{cases} 1, & n = 1 \\ 0, & \exists d > 1, d^{2} \mid n \\ (-1)^{\omega(n)}, & \text{otherwise}\end{cases}$ 可以用欧拉筛线性预处理。
总的复杂度 $\mathcal{O}(V\log V \cdot\omega(V))$。
```cpp
vector<int> f(V); // f[i]: 初始数组中数字 i 的出现次数
vector<int> g(V); // g[i]: 数字 i 当前是否可以被表示出来
for (auto x : a) {
f[x] = 1;
g[x] = 1;
}
for (int t = 1; ; t++) {
vector<int> G(V);
for (int i = 1; i < V; i++) {
int sumf = 0;
int sumg = 0;
for (int j = i; j < V; j += i) {
sumf += f[j];
sumg += g[j];
}
G[i] = sumf * sumg;
}
for (int i = 1; i < V; i++) {
g[i] = 0;
for (int k = 1; i * k < V; k++) {
g[i] += mu[k] * G[i * k];
}
}
if (g[d] > 0) {
cout << (t + n - 1) << endl;
return;
}
}
```
---
### Step 3 在变换域操作
有变换就必然有卷积与乘法的对应，在数论中，这个卷积是 GCD 卷积，
$$
c[k] = \sum_{\gcd(n, m) = k}^{} a[n] \cdot b[m]
\xleftrightarrow
[{\displaystyle x[n] = \sum_{d = 1}^ {\infty} \mu[d] \cdot X[n d]}]
{\displaystyle X[n] = \sum_{d = 1}^ {\infty} x[n d]}
C[k] = A[k] \cdot B[k]
$$
上面讲解中的 $G_{t}$ 实际上是 $f$ 和 $g_{t - 1}$ GCD 卷积的变换域表示，一个域的卷积对应于另一个域的乘法，$G_{t}[k]=F[k]\cdot G_{t-1}[k]$；而从 $G_{t}$ 倒推 $g_{t}$ 的过程，实际做了一次反 Mobius 变换。
从这个角度看，没有必要每次循环都先正变换再反变换。直接一直在变换域做点值乘法，
$$
G_{t} = \underbrace{ F \ast F \ast \dots \ast F }_{t \text{ times}}
$$
然后只判断 $g_{t}[d]$ 这一项是否大于 0。
复杂度 $\mathcal{O}(V\log V)$。
```cpp
vector<int> f(V); // f[i]: 初始数组中数字 i 的出现次数
for (auto x : a) {
f[x] = 1;
}
vector<int> F(V); // f 的变换域表示，原代码的 sumf
for (int i = 1; i < V; i++) {
for (int j = i; j < V; j += i) {
F[i] += f[j];
}
}
auto G = F; // g[0] 的变换域表示，原代码的 sumg
for (int t = 1; ; t++) {
for (int i = 1; i < V; i++) {
G[i] *= F[i]; // 做一次卷积 g[t] = g[t - 1] * f <=> G[t][i] = G[t][i] * F[i]
}
int res = 0; // 原代码的 g[t][d]，第 t 次变换后，d 的值
for (int k = 1; d * k < V; k++) {
res += mu[k] * G[d * k];
}
if (res > 0) {
cout << (t + n - 1) << endl;
return;
}
}
```
---
## Code
```cpp
#include <bits/stdc++.h>
using namespace std;
struct sieve {
vector<int> minp, primes;
vector<int> mu; // 莫比乌斯函数
sieve(int N = 1e6) : minp(N), mu(N) {
minp[1] = 1;
mu[1] = 1;
for (int n = 2; n < N; n++) {
if (!minp[n]) {
minp[n] = n;
primes.push_back(n);
mu[n] = -1;
}
for (int p : primes) {
if (1ll * n * p >= N) break;
minp[n * p] = p;
if (p == minp[n]) {
mu[n * p] = 0;
break;
}
mu[n * p] = -mu[n];
}
}
}
} sieve;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
for (int t = (cin >> t, t); t--; ) [] {
int n;
cin >> n;
vector<int> a(n);
int d = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
d = gcd(d, a[i]);
}
int cnt = ranges::count(a, d);
if (cnt) {
cout << (n - cnt) << endl;
return;
}
const int V = *ranges::max_element(a) + 1;
vector<int> f(V); // f[i]: 初始数组中数字 i 的出现次数
for (auto x : a) {
f[x] = 1;
}
vector<int> F(V); // f 的变换域表示，原代码的 sumf
for (int i = 1; i < V; i++) {
for (int j = i; j < V; j += i) {
F[i] += f[j];
}
}
auto G = F; // g[0] 的变换域表示，原代码的 sumg
for (int t = 1; ; t++) {
for (int i = 1; i < V; i++) {
G[i] *= F[i]; // 做一次卷积 g[t] = g[t - 1] * f <=> G[t][i] = G[t][i] * F[i]
}
int res = 0; // 原代码的 g[t][d]，第 t 次变换后，d 的值
for (int k = 1; d * k < V; k++) {
res += sieve.mu[k] * G[d * k];
}
if (res > 0) {
cout << (t + n - 1) << endl;
return;
}
}
} ();
return 0;
}
```
## 评注
1. 数论中很多东西不太大，比如素数距离和素因子个数等，看似有好几层循环实际上很小。
2. 「恰好」不好做，尝试转化为「至少」或「至多」，再反演得到结果。本题是把 GCD 恰好等于某数转化为 GCD 是某数的倍数。