题目详解

核心观察

设整个数组的全局最大公约数为：

$$g = \gcd(a_1, a_2, \dots, a_n)$$

结论1： 最终所有元素都会变成 $g$。

证明思路：

• 如果最终所有数都等于 $x$，则 $x$ 必须是每个原始 $a_i$ 的因数（因为操作只产生原数的因数），所以 $x \mid g$。
• 另一方面，任何操作得到的新数都是两个数的最大公约数，它至少是 $g$（因为 $g$ 能整除所有数，也能整除它们的最大公约数）。
• 因此 $x = g$。

---

分类讨论

情况1：$g$ 已经存在于数组中

若某个 $a_k = g$，则我们可以用它对其他元素执行操作：

对于每个 $a_i \neq g$，执行一次操作：$a_i := \gcd(a_i, a_k) = g$。

操作次数 = 数组中不等于 $g$ 的元素个数。

情况2：$g$ 不在数组中

我们需要先通过若干次操作，制造出一个等于 $g$ 的元素，然后再用这个元素去改变其他元素。

设用 $t$ 次操作得到 $g$，则总操作次数为：

$$t + (\text{不等于 } g \text{ 的元素个数})$$

注意：当 $g$ 被制造出来时，它所在的原始位置可能已经等于 $g$，但原来的那个元素可能已经改变了，不过这不影响计数。我们的策略是：先 制造出一个 $g$，然后对每个非 $g$ 元素做一次操作。

---

如何求最小 $t$

我们定义 $f[x]$ 表示：将一个元素变成 $x$ 所需的最少操作次数。

初始状态：

• 对于每个原始元素 $a_i$，$f[a_i] = 0$（不需要操作就已经是它本身）。

转移规则： 如果我们已经有办法在 $t$ 步内得到某个数 $x$，那么再执行一次操作（选择一个任意的 $a_j$ 作为“搭档”），就可以得到 $\gcd(x, a_j)$：

$$f[\gcd(x, a_j)] \le f[x] + 1$$

因为我们可以先花 $f[x]$ 步让某个位置变成 $x$，然后让目标位置与 $a_j$ 取 $\gcd$。

---

优化

直接按上述方程做，复杂度 $O(n \cdot \max(a) \cdot \log \max(a))$ 可能会超时。

预处理 $\gcd$

由于 $a_i \le 5000$，可以预处理所有 $x, y$ 的 $\gcd(x,y)$，存入二维数组 $g[x][y]$。预处理复杂度 $O(M^2)$，其中 $M = 5000$，这是可行的。

从大到小更新

因为 $\gcd(x, a_j) \le x$，所以我们从 $x = M$ 到 $1$ 枚举，这样能保证在更新 $f[\gcd(x, a_j)]$ 时，$f[x]$ 已经是最优值。

对于每个 $x$，遍历所有原始元素 $a_j$，进行转移。

最终我们关心的是 $f[1]$，因为当所有数都除以 $g$ 后，全局 $\gcd$ 变成了 $1$。

---

为什么除以 $g$ 后再处理？

代码中首先将整个数组除以 $g$，即 $a_i := a_i / g$。这样处理后，新数组的全局 $\gcd$ 为 $1$。

这样做的好处：

• 处理时数值范围不变（仍然是 $1 \sim 5000$），但目标变成了得到 $1$。
• 原问题等价于：在新数组中，先花 $f[1]$ 步制造出一个 $1$，然后让所有大于 $1$ 的元素都变成 $1$。

---

最终答案的计算

1. 先将所有 $a_i$ 除以 $g$。
2. 用 DP 计算出 $f[1]$，即制造一个 $1$ 的最少步数。
3. 如果数组中已经有 $1$，则 $f[1] = 0$，否则 $f[1] \ge 1$。
4. 总操作次数 = $f[1] + (\text{大于 }1\text{ 的元素个数})$。

注意：如果 $f[1] > 0$，意味着制造 $1$ 的过程本身会占用一个元素，这个元素在完成制造后已经变成 $1$，所以它 不需要再被额外转换一次。因此公式成立。

---

代码对应关系

k = g[k][a[i]];   // 计算全局 gcd
a[i] /= k;        // 除以全局 gcd
f[a[i]] = 0;      // 初始状态

for(int x = m ; x >= 1 ; x --) 
    for(int i = 1 ; i <= n ; i ++) {
        int y = a[i];
        checkmin(f[g[x][y]], f[x] + 1);
    }

ans = max(f[1] - 1, 0);          // 制造1的步数（如果本来有1则为0）
for(int i = 1 ; i <= n ; i ++) 
    if(a[i] > 1) ans ++;          // 把所有>1的变成1

注意：$f[1]$ 至少是 $1$（如果没有初始 $1$），但制造 $1$ 的过程可能已经改变了某个元素，所以 $f[1]$ 不能直接加，而是 $f[1] - 1$ 才是“净制造步数”。因此用 $\max(f[1] - 1, 0)$。

---

复杂度分析

• 预处理 $\gcd$：$O(M^2)$，$M = 5000$。
• 每个测试用例：$O(n \cdot M)$，其中 $M$ 是数组最大值。
• 总 $n$ 之和不超过 $5000$，所以最坏 $O(5000 \times 5000) = 2.5 \times 10^7$，可接受。

---

示例验证

样例1：$[12, 20, 30]$

• $g = 2$，除以 $g$ 得 $[6, 10, 15]$。
• 初始 $f[6] = f[10] = f[15] = 0$。
• 从大到小更新，可得到 $f[1]$：
  • $\gcd(15, 10) = 5$，$f[5] \le 1$
  • $\gcd(5, 6) = 1$，$f[1] \le 2$
• 所以 $f[1] = 2$，制造 $1$ 需 $2$ 步。
• 大于 $1$ 的元素有 $3$ 个，总操作数 = $2 + 3 = 5$？但答案给的是 $4$。

这里注意：实际上制造 $1$ 的过程中，那个变出 $1$ 的元素 原来也是大于 $1$ 的，所以它被计入了“大于 $1$ 的元素”中，但变成 $1$ 后不需要再操作一次。因此答案公式应为：

$$\text{总操作数} = f[1] + (\text{大于 }1\text{ 的元素个数}) - 1 $$

因为多算了一次。修正后：$2 + 3 - 1 = 4$，正确。

而代码中 ans = max(f[1] - 1, 0) 这一行实际上就是先做 $f[1] - 1$，然后后面再加非 $1$ 元素个数，等价于 $f[1] + (\text{非 }1\text{ 个数}) - 1$。