Orac and LCM

cf 641 A

证明

给定一个正整数序列 $a = \{a_1, a_2, \ldots, a_n\}$ ($n \ge 2$)。
定义多重集合 $t = \{ \text{lcm}(a_i, a_j) \mid 1 \le i < j \le n \}$，即所有不同元素对的最小公倍数 (LCM) 的集合。
我们的目标是计算 $g = \gcd(t)$，即集合 $t$ 中所有元素的最大公约数 (GCD)。

为了方便证明，我们定义：

• $g_k = \gcd(\{ \text{lcm}(a_k, a_i) \mid 1 \le i \le n, i \ne k \})$，即所有涉及 $a_k$ 的 LCM 对的 GCD。
• $d_k = \gcd(\{ a_i \mid 1 \le i \le n, i \ne k \})$，即除了 $a_k$ 外所有其他 $a_i$ 的 GCD。

证明 1：$g = \gcd(g_1, g_2, \ldots, g_n)$

我们需要证明 $g$ 与 $G = \gcd(g_1, g_2, \ldots, g_n)$ 相等。我们将通过证明 $g \mid G$ 和 $G \mid g$ 来完成。

部分 1：证明 $g \mid G$

1. 根据 $g = \gcd(t)$ 的定义，$g$ 必须整除集合 $t$ 中的每一个元素。即 $\forall 1 \le i < j \le n$, $g \mid \text{lcm}(a_i, a_j)$。
2. 考虑任意固定的 $k$ ($1 \le k \le n$)。对于所有 $i \ne k$，$g$ 必须整除 $\text{lcm}(a_k, a_i)$ （如果 $i < k$，则由步骤 1 直接得到；如果 $i > k$，也由步骤 1 直接得到）。
3. 因为 $g$ 整除集合 $\{ \text{lcm}(a_k, a_i) \mid i \ne k \}$ 中的每一个元素，所以根据 GCD 的性质，$g$ 必须整除这些元素的 GCD。即 $g \mid \gcd(\{ \text{lcm}(a_k, a_i) \mid i \ne k \})$。
4. 根据 $g_k$ 的定义，这意味着 $g \mid g_k$。
5. 由于 $g$ 整除 $g_k$ 对于所有的 $k = 1, \ldots, n$ 都成立，所以 $g$ 必须整除 $g_1, g_2, \ldots, g_n$ 的最大公约数。
6. 因此，$g \mid \gcd(g_1, g_2, \ldots, g_n)$，即 $g \mid G$。

部分 2：证明 $G \mid g$

1. 设 $G = \gcd(g_1, g_2, \ldots, g_n)$。根据 GCD 的定义，$G$ 整除每一个 $g_k$。
2. 考虑任意 $k$。我们知道 $G \mid g_k$ 且 $g_k = \gcd(\{ \text{lcm}(a_k, a_i) \mid i \ne k \})$。这意味着 $G$ 必须整除集合 $\{ \text{lcm}(a_k, a_i) \mid i \ne k \}$ 中的每一个元素。即 $\forall i \ne k$, $G \mid \text{lcm}(a_k, a_i)$。
3. 现在考虑集合 $t$ 中的任意元素 $\text{lcm}(a_i, a_j)$，其中 $i < j$。
4. 根据步骤 2，因为 $G \mid g_i$，所以 $G$ 整除所有涉及 $a_i$ 的 LCM 对，特别地，$G \mid \text{lcm}(a_i, a_j)$ （因为 $j \ne i$）。
5. 由于 $G$ 整除集合 $t$ 中的 每一个 元素 $\text{lcm}(a_i, a_j)$，所以根据 GCD 的定义，$G$ 必须整除集合 $t$ 中所有元素的 GCD。
6. 因此，$G \mid \gcd(t)$，即 $G \mid g$。

结论 1：
因为 $g \mid G$ 且 $G \mid g$，并且 $g, G$ 都是正整数（GCD 总是正的），所以 $g = G$。
即：$\gcd(t) = \gcd(g_1, g_2, \ldots, g_n)$。

证明 2：$g_k = \text{lcm}(a_k, d_k)$

我们需要证明 $\gcd(\{ \text{lcm}(a_k, a_i) \mid i \ne k \}) = \text{lcm}(a_k, \gcd(\{ a_i \mid i \ne k \}))$。

我们将使用 GCD 和 LCM 的一个重要的（类似分配律的）性质：
对于任意正整数 $X, Y_1, \ldots, Y_m$，有：

$$\gcd(\text{lcm}(X, Y_1), \text{lcm}(X, Y_2), \ldots, \text{lcm}(X, Y_m)) = \text{lcm}(X, \gcd(Y_1, Y_2, \ldots, Y_m))$$

证明该性质（使用素数幂分解）：
令任意素数 $p$。设 $X = p^{\alpha} \cdot X'$, $Y_j = p^{\beta_j} \cdot Y'_j$，其中 $X', Y'_j$ 不含素因子 $p$。

• 左侧 (LHS) 的 $p$ 的指数是：
  $\min(\max(\alpha, \beta_1), \max(\alpha, \beta_2), \ldots, \max(\alpha, \beta_m))$
• 右侧 (RHS) 的 $p$ 的指数是：
  $\max(\alpha, \min(\beta_1, \beta_2, \ldots, \beta_m))$

我们需要证明 $\min_{j}(\max(\alpha, \beta_j)) = \max(\alpha, \min_{j}(\beta_j))$。
设 $\beta_{\min} = \min_{j}(\beta_j)$。

• 情况 1: 如果 $\alpha \le \beta_{\min}$。
  • LHS: $\max(\alpha, \beta_j) \ge \alpha$ 且 $\max(\alpha, \beta_j) \ge \beta_j \ge \beta_{\min}$。因为 $\alpha \le \beta_{\min}$，所以对于某个 $j'$ 使得 $\beta_{j'} = \beta_{\min}$，我们有 $\max(\alpha, \beta_{j'}) = \beta_{\min}$。对于其他的 $\beta_j \ge \beta_{\min}$，有 $\max(\alpha, \beta_j) \ge \beta_{\min}$。所以 $\min_{j}(\max(\alpha, \beta_j)) = \beta_{\min}$。
  • RHS: $\max(\alpha, \min_{j}(\beta_j)) = \max(\alpha, \beta_{\min}) = \beta_{\min}$ (因为 $\alpha \le \beta_{\min}$)。
  • 两侧相等。
• 情况 2: 如果 $\alpha > \beta_{\min}$。
  • LHS: $\max(\alpha, \beta_j)$。因为 $\alpha > \beta_{\min}$，所以对于某个 $j'$ 使得 $\beta_{j'} = \beta_{\min}$，我们有 $\max(\alpha, \beta_{j'}) = \alpha$。对于其他的 $\beta_j \ge \beta_{\min}$，如果 $\beta_j \ge \alpha$，则 $\max(\alpha, \beta_j) = \beta_j \ge \alpha$；如果 $\beta_j < \alpha$，则 $\max(\alpha, \beta_j) = \alpha$。因此，所有 $\max(\alpha, \beta_j)$ 的值都 $\ge \alpha$，且至少有一个等于 $\alpha$。所以 $\min_{j}(\max(\alpha, \beta_j)) = \alpha$。
  • RHS: $\max(\alpha, \min_{j}(\beta_j)) = \max(\alpha, \beta_{\min}) = \alpha$ (因为 $\alpha > \beta_{\min}$)。
  • 两侧相等。

因此，该性质对于任意素数 $p$ 的指数都成立，故性质本身成立。

应用该性质：
在我们的问题中，令 $X = a_k$，令集合 $\{Y_1, \ldots, Y_m\}$ 为 $\{a_i \mid i \ne k\}$。
那么根据该性质：

$$\gcd(\{ \text{lcm}(a_k, a_i) \mid i \ne k \}) = \text{lcm}(a_k, \gcd(\{ a_i \mid i \ne k \}))$$

根据 $g_k$ 和 $d_k$ 的定义，上式即为：

$$g_k = \text{lcm}(a_k, d_k)$$

证明完毕。

最终结论

结合两个证明：

1. 我们需要计算 $g = \gcd(t)$。
2. 我们证明了 $g = \gcd(g_1, g_2, \ldots, g_n)$。
3. 我们证明了 $g_k = \text{lcm}(a_k, d_k)$，其中 $d_k = \gcd(a_i | i \ne k)$。

因此，最终的计算方法是：

$$g = \gcd(\text{lcm}(a_1, d_1), \text{lcm}(a_2, d_2), \ldots, \text{lcm}(a_n, d_n))$$

其中 $d_k$ 可以通过预计算前缀和后缀 GCD 来高效获得。

参考代码 ：

vector<long long> prefix(n);
vector<long long> suffix(n);
prefix[0] = arr[0];
for(int i = 1; i < n; ++i) {
    prefix[i] = std::gcd(prefix[i - 1], 1LL * arr[i]);
}
suffix[n - 1] = arr[n - 1];
for(int i = n - 2; i >= 0; --i) {
    suffix[i] = std::gcd(suffix[i + 1], 1LL * arr[i]);
}

long long ans = 0;
for(int i = 0; i < n; ++i) {
    long long k;
    if(i == 0) {
        k = suffix[1];
    } else if(i == n - 1) {
        k = prefix[n - 2];
    } else {
        k = std::gcd(prefix[i - 1] , suffix[i + 1]);
    }

    k = std::lcm(1LL * arr[i], k);
    if(k != 0) {
        ans = std::gcd(ans, k);
    } else {
        ans = k;
    }
}

cout << ans << nl;

---

下面我们换一种思路来理解

usaco guide

先看代码 ：

long long n , a , b;
input(n, a, b);

auto opt = [&]() {
    long long t = std::gcd(a,b);
    std::tie(a,b) = std::make_pair(t , a / t * b);
};

opt();
for(int i = 2; i < n; ++i) {
    long long t;
    input(t);
    b = std::gcd(b, t);
    opt();
}

cout << b << nl;

---

问题分析：对中最小公倍数的最大公约数

问题描述

给定一个包含 $n$ 个正整数的序列 $a = \{a_1, a_2, \dots, a_n\}$，其中 $n \ge 2$。
定义一个多重集 $t = \{ \text{lcm}(a_i, a_j) \mid 1 \le i < j \le n \}$。
目标是计算 $G = \gcd(t)$。

换句话说，我们需要计算：

$$G = \gcd \left( \{ \text{lcm}(a_i, a_j) \mid 1 \le i < j \le n \} \right)$$

算法概述（迭代方法）

维护两个变量，我们称之为 g 和 l（对应代码中的 a 和 b）。

在处理完前 $k$ 个元素 $\{a_1, \dots, a_k\}$ 后（其中 $k \ge 2$），这两个变量存储以下值：

• g = $G_k = \gcd(a_1, a_2, \dots, a_k)$
• l = $T_k = \gcd(\{ \text{lcm}(a_i, a_j) \mid 1 \le i < j \le k \})$

算法流程如下：

1. 初始化（使用 $a_1, a_2$）：计算 $G_2 = \gcd(a_1, a_2)$ 和 $T_2 = \text{lcm}(a_1, a_2)$。将它们存入 g 和 l。
2. 循环（从 $k = 3$ 到 $n$）：读取 $a_k$。使用前一步的 $G_{k-1}$、$T_{k-1}$ 和新元素 $a_k$ 来更新 g 为 $G_k$，l 为 $T_k$。
3. 结果：处理完 $a_n$ 后，存储在 l 中的值即为最终答案 $T_n$。

正确性证明

我们使用数学归纳法来证明该算法在每一步 $k$ 都能在变量 l 中正确计算出 $T_k$。

定义

• $G_k = \gcd(a_1, \dots, a_k)$
• $T_k = \gcd(\{ \text{lcm}(a_i, a_j) \mid 1 \le i < j \le k \})$ （我们在第 $k$ 步的目标值）
• $S_k = \gcd(\{ \text{lcm}(a_k, a_i) \mid 1 \le i < k \})$ （涉及新元素 $a_k$ 的所有配对的 lcm 的 gcd）

$T_k$ 的递推关系

满足 $1 \le i < j \le k$ 的数对 $(i, j)$ 可以分为两组：

1. $j < k$ 的数对：$\{ (i, j) \mid 1 \le i < j \le k-1 \}$
2. $j = k$ 的数对：$\{ (i, k) \mid 1 \le i < k \}$

根据 $\gcd$ 的性质 $\gcd(A \cup B) = \gcd(\gcd(A), \gcd(B))$，我们得到：

$$T_k = \gcd(\underbrace{\gcd(\{ \text{lcm}(a_i, a_j) \mid 1 \le i < j \le k-1 \})}_{T_{k-1}}, \underbrace{\gcd(\{ \text{lcm}(a_k, a_i) \mid 1 \le i < k \})}_{S_k})$$

$$T_k = \gcd(T_{k-1}, S_k)$$

关键恒等式

我们可以证明（通过素数分解和指数上的 min/max 运算）：

$$S_k = \gcd(\{ \text{lcm}(a_k, a_i) \mid 1 \le i < k \}) = \text{lcm}(a_k, \gcd(\{ a_i \mid 1 \le i < k \}))$$

$$S_k = \text{lcm}(a_k, G_{k-1})$$

组合递推公式

将上述恒等式代入 $T_k$ 的递推关系：

$$T_k = \gcd(T_{k-1}, \text{lcm}(a_k, G_{k-1}))$$

这就是算法在第 $k$ 步需要为变量 l 计算出的目标值。

分析代码的更新步骤

令 $\texttt{g}_{k-1}$ 和 $\texttt{l}_{k-1}$ 为处理 $a_k$ 之前的值。根据归纳假设，$\texttt{g}_{k-1} = G_{k-1}$ 且 $\texttt{l}_{k-1} = T_{k-1}$。代码执行：

1. 读取 $t = a_k$。
2. 计算中间值 $\texttt{l}_{\text{temp}} = \gcd(\texttt{l}_{k-1}, t) = \gcd(T_{k-1}, a_k)$。
3. 调用 $\texttt{opt}(\texttt{g}_{k-1}, \texttt{l}_{\text{temp}})$。设新值为 $\texttt{g}_k, \texttt{l}_k$。
   • $\texttt{g}_k = \gcd(\texttt{g}_{k-1}, \texttt{l}_{\text{temp}}) = \gcd(G_{k-1}, \gcd(T_{k-1}, a_k))$
   • $\texttt{l}_k = \text{lcm}(\texttt{g}_{k-1}, \texttt{l}_{\text{temp}}) = \text{lcm}(G_{k-1}, \gcd(T_{k-1}, a_k))$

我们需要验证：

1. 验证 $\texttt{g}_k = G_k$：
   我们需要证明 $\gcd(G_{k-1}, \gcd(T_{k-1}, a_k)) = \gcd(G_{k-1}, a_k)$。
   这个等式成立，因为 $G_{k-1} | a_i$ (对于 $i < k$)，这意味着 $G_{k-1} | \text{lcm}(a_i, a_j)$ (对于 $i < j < k$)，因此 $G_{k-1} | T_{k-1}$。令 $v_p(\cdot)$ 表示素数 $p$ 的指数。则 $v_p(G_{k-1}) \le v_p(T_{k-1})$。
   $v_p(\text{左}) = \min(v_p(G_{k-1}), \min(v_p(T_{k-1}), v_p(a_k))) = \min(v_p(G_{k-1}), v_p(a_k))$ （因为 $v_p(G_{k-1}) \le v_p(T_{k-1})$）。
   $v_p(\text{右}) = \min(v_p(G_{k-1}), v_p(a_k))$。
   由于所有素数 $p$ 的指数都匹配，等式成立。因此 $\texttt{g}_k = G_k$。

2. 验证 $\texttt{l}_k = T_k$：
   我们需要证明 $\text{lcm}(G_{k-1}, \gcd(T_{k-1}, a_k)) = \gcd(T_{k-1}, \text{lcm}(a_k, G_{k-1}))$。
   令 $g=v_p(G_{k-1}), t=v_p(T_{k-1}), v=v_p(a_k)$。我们需要证明 $\max(g, \min(t, v)) = \min(t, \max(v, g))$。
   我们已知 $g \le t$。当 $g \le t$ 时，这个关于非负整数的恒等式成立。它是整数在整除关系构成的格（Lattice）上的分配律的一种形式（其中 lcm $\leftrightarrow$ max，gcd $\leftrightarrow$ min 对应于指数运算）。
   由于所有素数 $p$ 的指数都匹配，等式成立。因此 $\texttt{l}_k = T_k$。

基础情况

对于 $k=2$，代码计算 $\texttt{g} = \gcd(a_1, a_2) = G_2$ 和 $\texttt{l} = \text{lcm}(a_1, a_2) = T_2$。基础情况成立。

结论

通过数学归纳法，我们证明了在处理完 $a_k$ 后，变量 l 正确地存储了值 $T_k$。因此，在处理完 $a_n$ 后，l 存储了 $T_n$，即为题目所求的答案 $G$。