最大公约数与最小公倍数

设 \(a_1,a_2\) 是两个整数，如果 \(d|a_1, \ d|a_2\)，那么 \(d\) 就称为 \(a_1\) 和 \(a_2\) 的公约数，其中最大的称为 \(a_1\) 和 \(a_2\) 的最大公约数，记作 \((a_1,a_2)\)。一般地，可以类似地定义 \(k\) 个整数 \(a_1,a_2,\cdots,a_k\) 的公约数和最大公约数，后者记作 \((a_1,\cdots,a_k)\)。

设 \(a_1,a_2\) 是两个整数，如果 \(a_1|l, \ a_2|l\)，那么 \(l\) 就称为 \(a_1\) 和 \(a_2\) 的公倍数，其中最小的称为 \(a_1\) 和 \(a_2\) 的最小公倍数，记作 \([a_1,a_2]\)。一般地，可以类似地定义 \(k\) 个整数 \(a_1,a_2,\cdots,a_k\) 的公倍数和最小公倍数，后者记作 \([a_1,\cdots,a_k]\)。

下面是 \(4\) 个有关最大公约数和最小公倍数的常见性质与结论。

1. 对任意整数 \(m\)，有 \(m(a_1,\cdots,a_k) = (ma_1, \cdots, ma_k)\)，即整数同时成倍放大，最大公约数也放大相同倍数。例如：\(9 = (9,18,27) = (3 \times 3, 3 \times 6, 3 \times 9) = 3 \times (3,6,9) = 3 \times 3 = 9\)。
   该性质同样适用于最小公倍数的情况。
2. 对任意整数 \(x\)，\((a_1,a_2) = (a_1, a_2 + a_1 x)\)，即一个整数加上另一整数的任意倍数，它们的最大公约数不变。例如：\((16, 10) = (16 - 10, 10) = (6, 10) = (6, 10 - 6) = (6, 4) = (6 - 4, 4) = (2, 4) = (2, 4 - 2 \times 2) = (2,0) = 2\)。
   这里要注意的是，\((a,0) = a\)。
   该性质不适用于最小公倍数的情况。
3. \((a_1, a_2, a_3, \cdots, a_k) = ((a_1, a_2), a_3, \cdots, a_k)\)，以及一个显然的推论 \((a_1, a_2, a_3, \cdots, a_{k+r}) = ((a_1, \cdots, a_k), (a_{k+1}, \cdots, a_{k+r}))\)。
   这是计算多元最大公约数的主要手段。
   例如求 \((12, 18, 21)\)，先求出 \((12, 18) = 6\)；再把 \(6\) 代入原式，求出 \((6, 21) = 3\)。连起来写就是 \((12, 18, 21) = ((12, 18), 21) = (6, 21) = 3\)。
   更深刻一点，这个性质说明了最大公约数运算具有某种“结合律”。
   该性质同样适用于最小公倍数的情况。
4. \([a_1,a_2](a_1,a_2)=a_1a_2\)，即最大公约数乘以最小公倍数等于原来两个数的乘积。
   例如 \((16,10) \times [16,10] = 2 \times 80 = 160 = 16 \times 10\)。

性质 \(2\) 可以给出一个高效的求两数最大公约数的算法：每次让较大的数对较小数取模（相当于较大数减了若干倍较小数，最高效地利用了性质 \(2\)，而且运用模运算时不必区分两数的大小），可以缩小问题规模而保持最大公约数不变，然后重复（递归）这个步骤。递归边界是某数变成了 \(0\)，而此时另一个数即为所求答案。

int gcd(int x, int y) {
    if (y == 0) return x; // 递归边界
    else return gcd(y, x % y);
}
也可以利用三目运算符
int gcd(int x, int y) {
    return y == 0 ? x : gcd(y, x % y);
}

这种利用两数相除（取模）求最大公约数的方法叫作辗转相除法或 Eculid 算法，最坏情况下的时间复杂度是 \(O(\log \max(x,y))\)。值得注意的是，相近规模下能让辗转相除执行次数最多（最坏情况）的数是相邻两个斐波那契数，而对于大多数情况，辗转相除法的计算效率都非常高。

利用性质 \(4\)，用两数之积除以它们的最大公约数，代码如下：

int lcm(int x, int y) {
    return x / gcd(x, y) * y; // 要注意乘除的先后顺序
}

因为 \(x\) 一定是 \(gcd(x,y)\) 的倍数，所以这样先除后乘没有问题，而且可以避免可能的溢出事件。

例题：删数

给定 \(n\) 个整数。对于其中的每个数 \(a_i\)，求出删去它以后剩下的所有数的最大公约数，\(n \le 10^6\)。例如，\(n = 5, a = [12, 36, 24, 18, 48]\)，则结果为 \([6, 6, 6, 12, 6]\)。

分析：到目前为止并没有直接的定理或者工具来维护删掉某个数以后的最大公约数，但是性质 \(3\) 说明，可以相对容易地把两堆最大公约数“拼”起来。对于删去 \(a_i\) 后的数组，显然剩下的数一定是 \(a_1\) 到 \(a_{i-1}\) 和 \(a_{i+1}\) 到 \(a_n\)，这分别是一段前缀和一段后缀。这意味着，如果用 \(left_i\) 表示 \(a_1\) 到 \(a_i\) 的最大公约数，\(right_i\) 表示 \(a_i\) 到 \(a_n\) 的最大公约数，那么删除 \(a_i\) 以后的答案就是 \((left_{i-1}, right_{i+1})\)，可以快速求出。

而 \(left\) 和 \(right\) 也可以利用性质 \(3\) 递推求出。

所以这道题的核心可以概括为：

• \(left_i = (a_1, \cdots, a_i) = ((a_1, \cdots, a_{i-1}), a_i) = (left_{i-1}, a_i)\)
• \(right_i = (a_i, \cdots, a_n) = (a_i, (a_{i+1}, \cdots, a_n)) = (a_i, right_{i+1})\)
• \(ans_i = (a_1, \cdots, a_{i-1}, a_{i+1}, \cdots, a_n) = ((a_1, \cdots, a_{i-1}), (a_{i+1}, \cdots, a_n)) = (left_{i-1}, right_{i+1})\)

例题：P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

给定某两个未知正整数 \((P,Q)\) 的最大公约数 \(x_0 \ (x_0 \le 10^5)\) 和最小公倍数 \(y_0 \ (y_0 \le 10^5)\)，求满足条件的所有可能的 \((P,Q)\) 的个数。

分析：根据题意可以得到 \(PQ=x_0y_0\)，既然 \(y_0\) 是 \(P,Q\) 的最小公倍数，那么 \(P,Q\) 必然是 \(y_0\) 的约数，因此可以枚举 \(y_0\) 的约数，假定为 \(P\)，从而求出 \(Q=\dfrac{x_0y_0}{P}\)，再检验这对 \(P\) 和 \(Q\) 是否满足条件。这样整个算法的时间复杂度就是枚举约数的时间复杂度，为 \(O(\sqrt{y})\)。

#include <cstdio>
using ll = long long;
int x0, y0;
ll gcd(ll x, ll y) {
    return y == 0 ? x : gcd(y, x % y);
}
int calc(ll p) {
    ll q = y0 / p * x0; // 注意x0*y0可能会爆int
    if (gcd(p, q) == x0) return 1;
    return 0;
}
int main()
{
    scanf("%d%d", &x0, &y0);
    int ans = 0;
    for (int i = 1; i * i <= y0; i++) {
        if (y0 % i == 0) {
            ans += calc(i);
            if (y0 / i != i) ans += calc(y0 / i); // 注意判断重复解
        }
    }
    printf("%d\n", ans);
    return 0;
}

例题：P1072 [NOIP2009 提高组] Hankson 的趣味题

已知正整数 \(1 \le a_0,a_1,b_0,b_1 \le 2 \times 10^9\)，设某未知正整数 \(x\) 满足 \((x,a_0)=a_1, \ [x,b_0]=b_1\)，求所有满足条件的正整数 \(x\) 的个数。\(2000\) 组数据。

分析：直接枚举 \(b_1\) 的约数再检验即可。

#include <cstdio>
using ll = long long;
int gcd(int x, int y) {
    return y == 0 ? x : gcd(y, x % y);
}
ll lcm(int x, int y) {
    return 1ll * x / gcd(x, y) * y;
}
void solve() {
    int a0, a1, b0, b1;
    scanf("%d%d%d%d", &a0, &a1, &b0, &b1);
    int ans = 0;
    for (int i = 1; i * i <= b1; i++) {
        if (b1 % i == 0) {
            if (gcd(i, a0) == a1 && lcm(i, b0) == b1) {
                ans++;
            }
            if (b1 / i != i) { // 注意重复判断
                if (gcd(b1 / i, a0) == a1 && lcm(b1 / i, b0) == b1) {
                    ans++;
                }
            }
        }
    }
    printf("%d\n", ans);
}
int main()
{
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        solve();
    }
    return 0;
}