# 欧几里得算法

又称辗转相除法,迭代求两数 gcd。

(a,b)=(a,ka+b)(a, b) = (a, ka + b) 的性质,gcd(a,b)=gcd(b,amodb)\gcd(a, b) = \gcd(b, a\bmod b)。容易证明这么做的复杂度是 O(logn)O(\log n)

注意:gcd(0,a)=a\gcd(0, a) = a

# 裴蜀定理

裴蜀定理:设 (a,b)=d(a, b) = d,则对任意整数 x,yx, y,有 d(ax+by)d|(ax + by) 成立;特别地,一定存在 x,yx, y 满足 ax+by=dax + by = d

等价的表述:不定方程 ax+by=c(a,b,c为整数)ax + by = c(a, b, c 为整数) 有解的充要条件为 (a,b)c(a, b)|c

# P4549 【模板】裴蜀定理

裴蜀定理可以推广到多元方程。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	
	int n; scanf("%d", &n); int a; scanf("%d", &a); int g = a; 
	for(int i=2; i<=n; ++i) {
		scanf("%d", &a); if(a == 0) continue;
		if(a < 0) a = -a;
		g = __gcd(g, a);
	}
	printf("%d\n", g);
	return 0;
}

# 扩展欧几里得(exgcd)

裴蜀定理的推论:a,ba, b 互质等价于 ax+by=1ax + by = 1 有解。

因此,要求不定方程 ax+by=cax+by=c 的解,只需求 ax+by=d,d=gcd(a,b)ax+by=d,d=\gcd(a,b) 的解,然后扩倍(乘上 cd\frac{c}{d})即可。

# 求出任意一个解

考虑使用欧几里德算法的思想,令 a=bq+ra = bq + r,其中 r=amodbr = a \bmod b,递归求出 bx+ry=dbx + ry = d 的一个解。

设求出 bx+ry=dbx + ry = d 的一个解为 x=x0,y=y0x = x_0, y = y_0,考虑如何把它变形成 ax+by=dax + by = d 的解。

a=bq+ra = bq + r 代入 ax+by=dax + by = d,化简得

b(xq+y)+rx=db(xq + y) + rx = d

xq+y=x0,x=y0xq + y = x_0, x = y_0

上式成立。

x=y0,y=x0y0qx = y_0, y = x_0 - y_0q

ax+by=dax + by = d 的解。

注意边界情况:当 b=0b = 0 时,必有 a=da = d,此时令 x=1,y=0x = 1, y = 0 即可。

# 怎么求出所有解?

先用 exgcd 求出任意一个解 x=x0,y=y0x = x_0, y = y_0,再求出 ax+by=0ax + by = 0 的最小的解

x=dx=b/(a,b),y=dy=a/(a,b)x = dx = b/(a, b), y = dy = -a/(a, b)

所有解就是

x=x0+kdx,y=y0+kdy,kZx = x_0 + kdx, y = y_0 + kdy,k\in \mathbb{Z}

# P1082 同余方程

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
ll a, b;
pll exgcd(ll a, ll b) {
	if(b == 0) return {1,0};
	pll p = exgcd(b, a%b);
	return {p.second, p.first-a/b*p.second};
}
int main() {
	
	scanf("%lld%lld", &a, &b);
	ll x = exgcd(a,b).first;
	while(x < 0) x+=b;
	while(x-b > 0) x-=b;
	printf("%lld\n", x);
	return 0;
}

# P3951 [NOIP2017 提高组] 小凯的疑惑

方法很多,这里提供一个比较好理解的扩欧做法。

首先已知题目必存在答案,那么设答案为 k1k-1 ,则 ax+by=kax+by=k 必有一组非负整数解 (x,y)(x,y)

假设 ax+by=k1ax+by=k-1 有非负整数解,那么该式必能化为

a(xx0)+b(yy0)=ka(x-x_0)+b(y-y_0)=k

其中

ax0+by0=1ax_0+by_0=1

注意到,若尽量使该式能够有解,则有两种情况,分别令 x0x_0y0y_0 取其最小非负整数解 xx'yy''(因为一方最小时另一方必为最大情况)

因此为了让原式无解,需保证 xx<0,yy<0x-x'<0, y-y''<0,即 x<x,y<yx<x',y<y''

因为要构造最大非负整数解,所以令 x=x1,y=y1x=x'-1,y=y''-1 所得即为 kk,答案即为 a(x1)+b(y1)1a(x'-1)+b(y''-1)-1,就可以直接利用扩欧求解了。

不过其实还能进一步化简

有一个很显然的结论,ax0+by0=1ax_0+by_0=1 是没有非负整数解的

然后把 x,yx,y 想象成分别在两个竖直的数轴上,可以发现,对于上面的两组解 (x,y),(x,y)(x',y'),(x'',y''),他们都是离水平面(原点)最近的解,所以他们在扩欧通解上是两组相邻的解

ans=k1=a(x1)+b(y1)1=axa+byb1=ax+by+abab1=abab.\begin{aligned} ans&=k-1\\ &=a(x'-1)+b(y''-1)-1 \\ &=ax'-a+by''-b-1 \\ &=ax'+by'+ab-a-b-1 \\ &=ab-a-b. \end{aligned}

更新于