跳到主要内容

AcWing 872. 最大公约数

本节目标

用欧几里得算法维护余数不变量，求非负最大公约数。

这是质因数、约数与最大公约数中最常复用的工具：不必枚举共同因子，只要不断用余数替换问题即可。

查看 AcWing 原题

题意与约束​

对多组整数 a, b 输出最大公约数。核心函数约定返回非负结果，并允许一个参数为零，例如 gcd(0, 5) = 5。C++ 返回 long long，因此输入含 INT_MIN 时也能表示最大可能结果 2147483648。

第一反应与瓶颈​

可以从 min(a, b) 向下寻找第一个同时整除两数的值，但相邻的大数会让这种方法接近线性。质因数分解也可求解，却为一个简单结果付出了额外工作。

数学关系与算法推导​

设 a = qb + r，其中 r = a mod b。一个数同时整除 a、b，就整除 r = a - qb；反过来同时整除 b、r 的数也整除 a = qb + r。因此 gcd(a, b) = gcd(b, r)。

先取两数绝对值，然后循环执行 (a, b) = (b, a mod b)，直到 b = 0。此时所有公因子都压缩到 a，且 gcd(a, 0) = a 给出零值边界。

正确性依据​

每次替换保持两个数的公因子集合不变，故最大公约数不变。第二个数的绝对值严格减小并最终为零，循环终止。终止状态为 (g, 0)，其正公约数就是 g 的约数，最大的非负公约数为 g 本身，因此返回值正确。

样例执行过程​

gcd(48, 18)：48 mod 18 = 12，变为 (18,12)；再变为 (12,6)、(6,0)，返回 6。gcd(0, 5) 第一步变为 (5,0)，返回 5。

代码实现​

C++17
#include <iostream>

using namespace std;

long long greatestCommonDivisor(int a, int b) {
    long long x = a;
    long long y = b;
    if (x < 0) {
        x = -x;
    }
    if (y < 0) {
        y = -y;
    }

    while (y != 0) {
        const long long remainder = x % y;
        x = y;
        y = remainder;
    }
    return x;
}

#ifndef ALGORITHM_TUTORIAL_TEST
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int count;
    cin >> count;
    while (count--) {
        int a;
        int b;
        cin >> a >> b;
        cout << greatestCommonDivisor(a, b) << '\n';
    }
}
#endif

核心函数只返回数值；完整程序读取每组整数并逐行输出。C++ 接口为 long long greatestCommonDivisor(int a, int b)：先把参数提升为 long long 再规范化符号，避免对 INT_MIN 直接取绝对值，也避免最终结果窄化；Python 同样返回非负结果。

复杂度分析​

余数序列快速缩小，时间复杂度为 O(1 + log(max(|a|, |b|) + 1))，额外空间为 O(1)；参数含零乃至两个参数都为零时仍由该表达式覆盖。

边界与易错点​

  • gcd(0, x) 应为 |x|，不是零。
  • 交换参数不应改变结果；相等参数应直接在一次余数后结束。
  • 先取绝对值，避免负数余数规则影响“非负 GCD”的接口约定。
  • C++ 必须先提升到更宽类型再处理 INT_MIN 的绝对值，且返回类型也要足以容纳 2147483648，不能直接调用 abs(int) 或把结果窄化回 int。

模式迁移​

GCD 可用于分数约分、最小公倍数、模运算中的互素判断，以及计算几何中斜率的分子分母规范化。后续出现“比例相同”或“共同周期”时，优先检查能否用它消去公共尺度。