最大公因数
2026-04-21
定义
公因数是指一个数是一组数中每个数的因数。
最大公因数是指公因数中最大的那个。
通常写作 gcd(a,b) 或 (a,b)。
欧几里得算法
对于两个数 a 和 b(a>b),怎么求它们的最大公因数呢?
显然,若 amodb=0,则 b 为两者最大公因数;若 amodb=0,则 gcd(b,amodb) 即为最大公因数,下面给出证明。
证明 gcd(a,b)=gcd(b,amodb)
令 a=k×b+c (0≤c<b)。
先证充分性。
设正整数 d 满足 d∣a 且 d∣b。
由于 c=a−k×b,则有 dc=da−k×db,此时右边都为整数,则 dc 也为整数,即 d∣c 成立。
因此,gcd(a,b)⇒gcd(b,amodb)。
再证必要性。
设正整数 d 满足 d∣c 且 d∣b。
由于 c+k×b=a,则有 dc+k×db=da,此时左边都为整数,则 da 也为整数,即 d∣a 成立。
因此,gcd(b,amodb)⇒gcd(a,b)。
那么复杂度怎么样呢?我们来讨论一下:
- 若 a<b,递归 gcd(b,a)。
- 若 a≥b,递归 gcd(b,amodb),显然 a 大小至少缩小一倍,而每发生一次 1,一定接着发生 2,即最多递归 logV 层。
即复杂度为 O(logmin(a,b))。
Stein 算法
由于大整数的除法及取模操作及其昂贵,而减法与位移操作很快,所以 Stein 算法诞生了。
具体原理是根据奇偶性进行分类:
- 若 a 和 b 都是偶数,显然 gcd(a,b)=2×gcd(2a,2b)。
- 若 a 为偶数,b 为奇数,显然 gcd(a,b)=gcd(2a,b)。
- 若 a 和 b 都是奇数,显然 gcd(a,b)=gcd(∣a−b∣,min(a,b))。
时间复杂度为 O(logV)。
扩展欧几里得算法
裴蜀定理 求对于不全为零的整数 a,b,ax+by=gcd(a,b) 的一组整数解 (x,y)。
对于当前的 a,b,考虑进行分讨:
- b=0 时,显然一组解为 x=1,y=0。
- 对于下一层状态 (b,amodb) 的解 x′,y′,显然有 bx′+(amodb)y′=gcd(b,amodb),将 amodb=a−a×⌊ba⌋ 带入并整理,得到 bx′+(a−a×⌊ba⌋)y′=gcd(a,b),其中 gcd(a,amodb)=gcd(a,b)。
然后,考虑把这个式子写成 ax+by=gcd(a,b) 的形式,也就是 a⋅y′+b⋅(x′−⌊ba⌋),所以回溯公式为:
{x=y′y=x′−⌊ba⌋⋅y′
那么如何从 ax+by=gcd(a,b) 扩展到 ax+by=c 呢?
显然,必须有 gcd(a,b)∣c。
有了这个大前提,我们先对 gcd(a,b) 求出一组特解 x0 和 y0,然后将其扩倍,显然现在的一组解是 x1=x0×gcd(a,b)c、y1=y0×gcd(a,b)c。
有了这组特解,我们可以写出通解公式:
{x=x1+k×gcd(a,b)by=y1−k×gcd(a,b)a(k∈Z)
直观的讲,就是在满足 ax+by=c 的情况下将 x,y 进行一增一减来构造所有解。
特别的,如果想要求出最小的 x>0,则答案为 xmin=(x1modm+m)modm(其中 m=gcd(a,b)b)
LL exgcd(LL a , LL b , LL &x , LL &y) {
if (!b) {
x = 1; y = 0;
return a;
}
LL d = exgcd(b , a % b , y , x);
y -= a/b*x;
return d;
}