3014 字

15 分钟

【ACM 算法题单】GCD相关问题

2026-03-12

Algorithm

/

GCD单调收敛问题#

在涉及区间或子数组的数论问题中，GCD 运算展现出一种极强的 单调收敛性 。随着参与运算的元素数量增加，其结果呈现出只减不增的态势。从代数角度看，每当一个新元素加入运算，当前的 GCD 值要么保持不变，要么转化为原值的一个真因子。这种性质意味着，当我们以某个固定位置为起点向一侧扩展子数组时，其 GCD 值会形成一个递减的链条，并最终收敛于一个稳定状态。

这一性质引申出一个核心结论：固定单一端点时，子数组的 GCD 种类极其有限 。由于每次 GCD 值的改变都意味着至少失去一个质因子，一个数值为 $V$ 的元素在不断取 GCD 的过程中，其值发生变化的次数不会超过 $O(\log V)$ 次。因此，尽管长度为 $N$ 的序列拥有 $O(N^2)$ 个子数组，但若以 GCD 值进行状态归类，整个序列中本质不同的 GCD 状态数仅为 $O(N \log V)$ 。

这种信息的高度压缩性，使得 GCD 相关的区间问题往往可以从暴力枚举转化为 对状态跳变点的维护 。在算法实现中，我们可以利用这种类似于取最小值运算的收缩性质，实时维护以当前位置为终点的所有不同 GCD 值及其对应的区间范围。由于状态数受限在对数级别，这种做法能将原本需要平方复杂度的统计问题，优化至近线性效率。

最大公约数变换#

题目链接

题目要点解析#

数组置一的次数#

题目链接

题目要点解析#

GCD更相减损问题#

加入差值的绝对值直到长度固定#

题目链接

题目要点解析#

GCD倍数枚举问题#

在处理 GCD 相关的构造或计数问题中，一个极具启发性的思路是 围绕目标值反推可选元素集合 。如果我们希望通过一组数的运算得到特定的公约数 $g$ ，最直观的观察是：所有参与运算的元素必须都是 $g$ 的倍数。这一简单的整除约束，实际上为我们圈定了所有潜在的候选对象。若一个数不是 $g$ 的倍数，它在任何包含它的集合中都会破坏 $g$ 作为公约数的可能性。

基于这一逻辑，倍数枚举 成为了验证目标值是否可行的核心手段。在实际建模时，我们可以通过枚举潜在的 GCD 值 $g$ ，并将原数组中所有 $g$ 的倍数提取出来进行整体 GCD 运算。如果这些倍数的最大公约数恰好等于 $g$ ，则说明该目标值在原数组中是可构造的；反之，若结果大于 $g$ ，则说明没有任何子集能精确收敛到 $g$ 。这种方法将复杂的子集搜索转化为了值域上的倍数扫描，利用类似埃氏筛的结构化枚举，大幅降低了状态处理的复杂度。

这种从倍数关系入手的视角，同样是解决 LCM 问题的关键。由于 LCM 与 GCD 之间存在互补关系，LCM 的变化往往受到 GCD 取值的约束。相比于 LCM 在数值空间中极易发生不受控的倍数扩张，GCD 始终被限制在值域的约数结构之内。因此直接处理 LCM 往往难以控制搜索边界，而通过 枚举 GCD 来间接约束 LCM 则显得更为高效。

多重集子集查询#

题目链接

题目要点解析#

最小公倍数连通#

题目链接

题目要点解析#

GCD和式变换问题#

在数论问题中，经常会遇到涉及两个变量的嵌套求和式。例如既要枚举 $i$ ，又要枚举 $j$ ，并且两者之间通过某种函数相结合。如果直接枚举所有数对，时间复杂度将达到 $O(n^2)$ ，在数据范围较大时无法接受。

因此这类问题需要通过 和式变换 来重新组织计算过程，其核心是利用对象交换贡献法：我们不再逐个枚举变量所有可能的值，而是从 “某个计算结果出现了多少次” 的角度进行统计。

以经典的 GCD 全局求和为例：

\sum_{i=1}^{n} \sum_{j=1}^{n} \gcd(i, j)

如果按照定义直接计算，那么需要枚举所有 $n^2$ 个数对。为了降低复杂度，可以换一种思路来求解这个式子：对于每一个可能的最大公约数 $k$ ，统计有多少对 $(i,j)$ 满足 $\gcd(i,j) = k$ ，然后乘上 $k$ 作为贡献。

按照这个思路，可以把原来的求和改写为先枚举最大公约数的取值，再统计满足条件的数对数量：

\sum_{i=1}^{n} \sum_{j=1}^{n} \gcd(i, j) = \sum_{k=1}^{n} k \sum_{i=1}^{n} \sum_{j=1}^{n} \big[\gcd(i, j) = k\big]

接下来需要解决如何统计满足 $\gcd(i,j) = k$ 的数对数量。假设某一对数满足 $\gcd(i,j) = k$ ，那么 $i$ 和 $j$ 一定都包含因子 $k$ ，也就是说可以把它们写成 $i = kx$ 、 $j = ky$ 。把这个形式代入 $\gcd(i,j)$ ，可以得到：

\gcd(i,j)=\gcd(kx,ky)=k\gcd(x,y)

为了让 $\gcd(i,j) = k$ 成立，就必须满足 $\gcd(x,y) = 1$ 。换句话说，当我们把 $i$ 和 $j$ 同时除以 $k$ 之后，得到的两个数必须是互质的。同时还需要考虑范围的变化：由于 $i \leq n$ 且 $j \leq n$ ，代入 $i = kx$ 、 $j = ky$ 后可以得到 $x \leq \lfloor n/k \rfloor$ 、 $y \leq \lfloor n/k \rfloor$ 。因此原本的问题，就转化为了在 $1$ 到 $\lfloor n/k \rfloor$ 的范围内统计互质数对：

\sum_{k=1}^{n} k \sum_{x=1}^{\lfloor n/k \rfloor} \sum_{y=1}^{\lfloor n/k \rfloor} \big[\gcd(x,y) = 1\big]

为了统计互质数对，可以利用欧拉函数的定义：欧拉函数 $\varphi(t)$ 表示在 $1$ 到 $t$ 的整数中，与 $t$ 互质的数的个数。也就是说，如果固定第二个数 $y = t$ ，那么满足 $\gcd(x,t) = 1$ 的 $x$ 一共有 $\varphi(t)$ 个。

因此可以按第二个数来统计互质数对：对于 $y = 1, 2, 3, \ldots, m$ ，分别计算与它互质的 $x$ 的数量，然后全部加起来。如果只统计满足 $x \leq y$ 的数对，那么互质数对的数量就是：

\sum_{i=1}^{m} \varphi(i)

不过原问题中 $x$ 和 $y$ 是完全对称的：如果 $(x,y)$ 是一对互质数，那么 $(y,x)$ 也是一对互质数，因此每一个满足 $x<y$ 的数对都会对应一个对称的位置，只有对角线上的 $(1,1)$ 不会产生新的对称点。因此在整个 $m \times m$ 的网格中，互质数对的总数量可以写成：

2\sum_{i=1}^{m}\varphi(i)-1

这里乘 $2$ 是因为补上对称的那一半，而减去 $1$ 是因为 $(1,1)$ 被计算了两次。最后把 $m = \lfloor n/k \rfloor$ 代回原来的式子，就可以得到整个求和的最终形式：

\sum_{k=1}^{n} k \left(2\sum_{i=1}^{\lfloor n/k \rfloor}\varphi(i)-1\right)

经过这一步变换之后，原本需要枚举所有数对的双重循环，就转化为了枚举 $k$ 的单层循环。在实际实现时，只需要用筛法预处理出欧拉函数，并计算它的前缀和，就可以高效地完成整个计算。

欧拉函数反演#

在深入理解 GCD 和式变换后，我们可以将这一技巧推广为一种更具普适性的工具，即 欧拉反演 。欧拉反演的核心思想是降维，它能够复杂的 $\gcd(i, j)$ 函数拆解，转化为对约数的枚举，从而简化计算逻辑。

欧拉反演的理论基础源于欧拉函数的经典恒等式：

n = \sum_{d \mid n} \varphi(d)

该公式表明，任何正整数 $n$ 都可以表示为其所有约数的欧拉函数之和。当面对经典的 GCD 全局求和时，可以将 $\gcd(i, j)$ 带入欧拉恒等式中：

\sum_{i=1}^{n} \sum_{j=1}^{n} \gcd(i, j) = \sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{d \mid \gcd(i, j)} \varphi(d)

关键步骤在于 交换求和顺序：我们不再先枚举 $i$ 和 $j$ ，而是优先枚举因子 $d$ 。由于 $d \mid \gcd(i, j)$ 等价于 $d$ 同时整除 $i$ 和 $j$ ，在 $1$ 到 $n$ 的范围内，符合条件的 $i$ 的个数为 $\lfloor n/d \rfloor$ ，对应的 $j$ 也有 $\lfloor n/d \rfloor$ 个，因此每个 $\varphi(d)$ 的贡献次数为 $\lfloor n/d \rfloor^2$ 。最终可得公式：

\sum_{i=1}^{n} \sum_{j=1}^{n} \gcd(i, j) = \sum_{d=1}^{n} \varphi(d) \cdot \left\lfloor \frac{n}{d} \right\rfloor^2

这种推导在代数形式上更加简洁，避免了对称性处理中的繁琐细节。在算法实现上，结合线性筛预处理欧拉函数前缀和以及数论分块技术，可以将计算复杂度降低至 $O(\sqrt{n})$ ，适用于大规模数据计算。欧拉反演不仅是处理 GCD 和式问题的高效方法，也为深入理解数论反演（如莫比乌斯反演）奠定了基础。

莫比乌斯反演#

在深入理解欧拉反演之后，我们进一步介绍数论中极为重要的工具，即 莫比乌斯反演 。如果说欧拉反演是通过数值拆解来消除 GCD 的耦合关系，那么莫比乌斯反演则利用 容斥原理 在因数空间上建立了一套精密的计数机制。它不仅能够处理 GCD 求和，更适用于带有 “恰好等于” 约束的计数问题，其核心在于利用 莫比乌斯函数 $\mu(d)$ 的性质，将示性函数转化为可枚举的求和形式。

莫比乌斯反演的理论基础源于莫比乌斯函数的经典恒等式：

\sum_{d \mid n} \mu(d) = [n = 1]

该公式表明，只有当 $n = 1$ 时，所有因子的 $\mu$ 值之和为 $1$ ，否则为 $0$ 。在处理 GCD 问题时，这为我们去掉示性函数提供了严密的工具。当我们希望统计满足 $\gcd(i, j) = k$ 的数对时，可以先提取公因数 $k$ ，也就是将条件缩放为 $\big[\gcd(i/k, j/k) = 1\big]$ ，然后利用上述性质将条件逻辑转化为因子求和：

\Big[\gcd(\frac{i}{k}, \frac{j}{k}) = 1\Big] = \sum_{d \mid \gcd(i/k, j/k)} \mu(d)

接下来，通过 交换求和顺序 将因子 $d$ 提到最外层，原本相互耦合的 $i$ 和 $j$ 变为 $kd$ 的倍数。在 $1$ 到 $n$ 的范围内，满足条件的 $i$ 和 $j$ 的个数均为 $\lfloor n/(kd) \rfloor$ 。这一变换的核心在于利用 $\mu(d)$ 的正负抵消性，将 “恰好互质” 的复杂统计转化为对 “公约数倍数” 的简单计数。最终，原本带有 GCD 约束的和式可重写为：

\sum_{i=1}^{n} \sum_{j=1}^{n} \big[\gcd(i, j) = k\big] = \sum_{d=1}^{\lfloor n/k \rfloor} \mu(d) \cdot \left\lfloor \frac{n}{kd} \right\rfloor^2

莫比乌斯反演的优势在于其高度通用性。与欧拉反演不同，它不依赖于 $n$ 可以拆解为约数和的特定性质，而是建立在更基础的 容斥逻辑 上。这意味着无论是非对称求和范围 $n \neq m$ ，还是更复杂的倍数关系，莫比乌斯反演都能保持统一且标准的推导模式。在实际算法实现中，结合线性筛预处理莫比乌斯函数前缀和以及整除分块技术，莫比乌斯反演同样可以将计算复杂度降至亚线性量级，是处理高阶数论计数问题的重要工具。