本篇博客是【数论专题】系列的第 \(3\) 篇，希望大家多多支持。
最大公约数指两个整数 \(a,b\) 公有的因数中最大的数，记作 \(\gcd(a,b)\)。
辗转相除法
辗转相除法用来求两个数的最大公约数，又称欧几里得算法，其核心为：\(\gcd(x,y) = \gcd(y, x\bmod\ y)\)。
证明：
- 若 \(x < y\)，则 \(\gcd(y, x\bmod\ y) = \gcd(y, x) = \gcd(x,y)\)。
- 若 \(x\ge y\)，设 \(x = q\times y + r\)，其中 \(0\le r < y\)，显然 \(r = x\bmod\ y\)。对于 \(x,y\) 的任意公约数 \(d\)，因为 \(d\mid x,d\mid q\times y\)，所以 \(d\mid (x - q\times y)\)，即为 \(d\mid r\)，因此 \(d\) 为 \(y, r\) 的公约数。
辗转相除法的流程如下：
- 若 \(y = 0\)，则说明答案为 \(x\)。
- 若 \(y\ne 0\)，则根据 \(\gcd(x, y) = \gcd(y, x\bmod\ y)\) 往下递归。
时间复杂度 \(O(\log \min(x,y))\)。
int gcd(int x, int y)
{if(y == 0) return x;//y = 0 则返回答案 return gcd(y, x % y);//否则继续递归
}
最小公倍数
最小公倍数指两个整数 \(a,b\) 公有的倍数中最小的数，记作 \(\text{lcm}(a,b)\)。
定理：\(x\times y = \gcd(x, y) \times \text{lcm}(x, y)\)。
根据以上定理，可以得出 \(\text{lcm}(x, y) = x\times y\div \gcd(x, y)\)。
用辗转相除法求出 \(\gcd(x, y)\) 然后直接计算就行了，时间复杂度与辗转相除法一样。
int gcd(int x, int y)
{if(y == 0) return x;return gcd(y, x % y);
}
int lcm(int x, int y)
{return x * y / gcd(x, y);
}