目录
1. 最大公约数 (gcd)
数论中,通常用 \(d\ |\ a\) 表示 \(d\) 能整除 \(a\),即 \(d\) 是 \(a\) 的约数,用 \(d\not | \ a\) 表示 \(d\) 不是 \(a\) 的约数。
已知正整数 \(a,b\),如何求 \(g=gcd(a,b)\)?
1.1 更相减损术
- 若 \(a\geqslant b\),则 \(gcd(a,b)=gcd(b,a-b)\)
证明很简单,因为 \(a,b\) 都是 \(g\) 的倍数,所以设 \(a=k_{1}g,b=k_{2}g\),显然有 \(gcd(k_{1},k_{2})=1\),\(gcd(b,a-b)=gcd(k_{2}g,(k_{1}-k_{2})g)=g\cdot gcd(k_{2}g,(k_{1}-k_{2}))\)。
证明一下 \(gcd(k_{2},(k_{1}-k_{2}))=1\) 即可,可以假设它不为 \(1\) 然后反证,最后肯定能证明等式成立。
如果 \(a\gg b\),更相减损术的时间复杂度会达到最差的 \(O(a)\)
考虑这样一个优化:
如果 \(2\ |\ a,2\ |\ b\),则 \(gcd(a,b)=2\ gcd(\dfrac{a}{2},\dfrac{b}{2})\)
如果仅有 \(2\ |\ a\),\(gcd(a,b)=gcd(\dfrac{a}{2},b)\),仅有 \(2\ |\ b\) 时同理
优化后的算法也叫 Stein 算法
实现:
int gcd(int a, int b) {
a = abs(a), b = abs(b);
if (a == 0 || b == 0) return a + b;
int atimes = 0, btimes = 0;
while (~a & 1) {
a >>= 1;
++atimes;
}
while (~b & 1) {
b >>= 1;
++btimes;
}
do {
while (~a & 1) a >>= 1;
while (~b & 1) b >>= 1;
if (a < b) swap(a, b);
a -= b;
} while (a);
return b << min(atimes, btimes);
}
时间复杂度分析
\(2\ |\ a,2\ |\ b\) 时,每次循环会让 \(a,b\) 各减少一半。
否则仅有 \(2\ |\ a\) 或 \(2\ |\ b\),每次循环会让 \(a,b\) 之一减少一半。
否则一定有 \(2\ | (a-b)\)。
综上,时间复杂度是 \(log\) 级别的,至于是 \(log\) 多少,没算,懒得算,总之一定不会超过 \(O(log(a+b))\)。
1.2 辗转相除法 (欧几里得算法)
- \(gcd(a,b)=gcd(b,a\ mod\ b)\)
证明也很简单:
\(a<b\) 时显然成立
\(a\geqslant b\) 时,不妨设 \(a=qb+r\ (r=a\ mod\ b<b)\),因为 \(a,qb\) 都是 \(g\) 的倍数,所以 \(a-qb=r\) 也是 \(g\) 的倍数,反之亦成立,所以 \(a,b\) 的公约数集合与 \(b,a\ mod\ b\) 相同。
实现:
int gcd(int a, int b) {
while (b) { // b = 0 时 gcd(a, b) = a,此时退出循环返回 a 即可
a %= b;
swap(a, b);
}
return a;
}
或者写成递归形式,用条件运算符一行解决:
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
时间复杂度分析
如果传入的参数是 \(a<b\),只要经过一次循环就变成 \(a>b\),并且后面对 \(b\) 取模时也一定有 \(a>b\)。
当 \(a\geqslant b\),对 \(b\) 取模后 \(a\) 会减小一半以上,所以取模次数是 \(O(log\ a)\) 的。
综上,时间复杂度是 \(O(log(max\{a,b\}))\)。
由于 Stein 算法不涉及取模,相对而言在常数上略占优势,但由于欧几里得算法实现简单,所以后者在竞赛中更常用。
2. 最小公倍数 (lcm)
- 对任意正整数 \(a,b\),恒有 \(gcd(a,b)\times lcm(a,b)=a\times b\)
证明:
在认为 \(a,b\) 包含相同质因子的前提下对 \(a,b\) 作质因数分解:
\(a=p_{1}^{c_{1}}p_{2}^{c_{2}}...p_{n}^{c_{n}}\)
\(b=p_{1}^{d_{1}}p_{2}^{d_{2}}...p_{n}^{d_{n}}\)
\(gcd(a,b)=p_{1}^{min\{c_{1},d_{1}\}}p_{2}^{min\{c_{2},d_{2}\}}...p_{n}^{min\{c_{n},d_{n}\}}\)
\(lcm(a,b)=p_{1}^{max\{c_{1},d_{1}\}}p_{2}^{max\{c_{2},d_{2}\}}...p_{n}^{max\{c_{n},d_{n}\}}\)
因为 \(min\{c_{i},d_{i}\}+max\{c_{i},d_{i}\}=c_{i}+d_{i}\),所以 \(gcd(a,b)\times lcm(a,b)=a\times b\)
所以只要求出 \(gcd(a,b)\),就能 \(O(1)\) 求出 \(lcm(a,b)\)
实现:
int lcm(int a, int b) { return a / gcd(a, b) * b; } // 最好像这样先除再乘以免溢出
如果你不想手写这两个函数,C++17 起可以直接用 <numeric>
头文件中的 std::gcd
和 std::lcm
。
3. 裴蜀定理 (贝祖定理)
- 关于 \(x,y\) 的二元一次不定方程 \(ax+by=n\ (a,b,n\in \Z)\) 有整数解的充要条件是 \(gcd(a,b)\ |\ n\)。
证明略。 同学们可以尝试一下它的证明。
贝祖定理可以推广至三元及以上一次不定方程:
- \(ax+by+cz=n\) 有整数解 \(\lrArr n\ |\ gcd(a,b,c)\ (a,b,c,n\in \Z)\)
3.1 扩展欧几里得算法 (exgcd)
扩展欧几里得算法能在求出 \(gcd(a,b)\) 的同时顺带求出 \(ax+by=gcd(a,b)\) 的一组特解。
还记得如何求递归求 \(gcd(a,b)\) 吗?
- 递归: 求出 \(gcd(b,a\ mod\ b)\),就相当于求出了 \(gcd(a,b)\)
- 递归终点: \(b=0,gcd(a,0)=a\)
根据这个递归过程,我们可以考虑这样设计 \(exgcd\) 函数:
\(exgcd(a,b)\) 用于求出满足不定方程 \(ax+by=g\) 的三个整数 \(x,y,g\),其中 \(g=gcd(a,b)\)
-
递归: 先求出 \(exgcd(b, a\ mod\ b)=(x_{0},y_{0},g)\),考虑如何用它反推出 \(exgcd(a,b)=(x,y,g)\)
显然有以下等式:
\(ax+by=bx_{0}+(a\ mod\ b)y_{0}=g\)
\(ax+by=bx_{0}+(a-\lfloor\dfrac{a}{b}\rfloor b)y_{0}\)
\(ax+by=ay_{0}+bx_{0}-\lfloor\dfrac{a}{b}\rfloor b y_{0}\)
\(ax+by=ay_{0}+b(x_{0}-\lfloor\dfrac{a}{b}\rfloor y_{0})\)
由此得到一组特解: \(x=y_{0},y=(x_{0}-\lfloor\dfrac{a}{b}\rfloor y_{0})\)
-
递归终点: \(b=0\),解得 \(x=1,y=0,g=a\)
实现:
tuple<int, int, int> exgcd(int a, int b) {
if (b == 0) return {1, 0, a};
auto [x0, y0, g] = exgcd(b, a % b);
int x = y0;
int y = x0 - a / b * y0;
return {x, y, g};
}
习题:
abc340_f S = 1