【算法学习笔记】34：扩展欧几里得算法

裴蜀定理

描述

对于任意正整数$a$、$b$，一定存在整数系数$x$，$y$，使得：
$$ax+by=gcd(a,b)$$

并且$gcd(a,b)$是对于任意的系数$x$和$y$放在$a$和$b$上能凑出的最小正整数。

证明

如下如果有整数系数$x$、$y$，那么$ax+by$一定是$gcd(a,b)$的倍数，因为$a$和$b$都分别是$gcd(a,b)$的倍数。因此能凑出来的数字最小就是$gcd(a,b)$。

接下来证明一定存在$x$、$y$能凑出$gcd(a,b)$。证明存在性的东西可以用构造法，只要把这个东西构造出来了，那么就一定存在了。这个构造的方法就是扩展欧几里得算法，使得对于任意的$a$、$b$，都能构造出来$x$、$y$使得$ax+by=gcd(a,b)$。

扩展欧几里得算法

欧几里得算法是$gcd(a,b)=gcd(b,amodb)$，递归出口是当$b$为$0$时返回$a$，因为$0$和任何数的最大公约数就是那个数。

扩展欧几里得算法则是在欧几里得算法的基础上，把系数$x$和$y$构造出来。

考虑到欧几里得算法的递归特性，可以用之前递归出的结果计算出前面的结果。

如，欧几里得算法计算gcd的递归出口是$b$为$0$时返回$a$，此时$a$和$b$的最大公约数就是$a$，要使得$ax+by=a$，显然有一组整数解$x=1$且$y=0$。

考虑除了递归出口之外的递归分支，需要计算$gcd(b,amodb)$，假设此时已经求出一组解$y$和$x$（这里将$y$和$x$调换便于计算，不调换也是可以的，结论是另一种写法公式），即使得：
$$by+(amodb)x=gcd(b,amodb)=gcd(a,b)$$

考虑到$amodb=a-\lfloor \frac{a}{b}\rfloor \cdot b$，整理一下$a$和$b$的系数，得到：
$$ax+(y-\lfloor \frac{a}{b}\rfloor \cdot x)b=gcd(a,b)$$

因此，从上一组解的$x$不变，$y$减去$\lfloor \frac{a}{b}\rfloor \cdot x$就是为$a$和$b$构造的系数解。

#include <iostream>using namespace std;int exgcd(int a, int b, int& x, int& y) {if (!b) {x = 1, y = 0;return a;}int d = exgcd(b, a % b, y, x);y -= a / b * x;return d;
}int main() {int t; cin >> t;while (t -- ) {int a, b; cin >> a >> b;int x, y;exgcd(a, b, x, y);cout << x << ' ' << y << endl;}return 0;
}