一、理解和感悟
1、裴蜀定理
裴蜀定理（或贝祖定理）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数(a)、(b)和它们的最大公约数(d)，关于未知数(x)和(y)的线性不定方程（称为裴蜀等式）：若(a),(b)是整数,且(gcd(a,b)=d)，那么对于任意的整数(x),(y),(ax+by)都一定是(d)的倍数，特别地，一定存在整数(x),(y)，使(ax+by=d)成立。
推论：(a),(b)互质的充分必要条件是存在整数(x),(y)使(ax+by=1)。
举个栗子：
(2x+y=3)
那么(a=2),(b=1),(m=3),(gcd(2,1)=1),(3)是(1)的倍数，所以这个方程一定要整数解。
比如(x=1),(y=1)就是一个整数解，还可以有(x=-2),(y=7)也是一组整数解。
注意：如果一个二元一次方程有正整数解，那么不只是一组解。
再举一个栗子：
(4x+2y=5)
有没有整数解呢？没有，因为(a=4,b=2,m=5,gcd(4,2)=2,5)是除不开(2)的，所以没有整数解!
2、如何求贝祖数？
什么是贝祖数？
比如：(2x+y=3)，那么符合这个等式的(x=1),(y=1)就是一组贝祖数。
在计算机算法中，可以使用扩展欧几里得算法求贝祖数。
举个栗子：
求 (104x+40y=8) ，有没有合适的(x,y),也就是求贝祖数。
通过贝祖定理看一下，它是不是有解： (gcd(104,40)=8),(8)是(8)的倍数，所以此方程一定有解，那么解是什么呢？
扩展欧几里得算法的推导过程：
我们先来求方程 (ax+by=gcd(a,b))的解
((1))、当 (b=0)时
(ax+by=gcd(a,0))，也就是:(ax=gcd(a,0)=a),所以(x=1)。
那么(y)呢？因为普遍意义上的求贝祖数，一般是指不小于零的一组解，那么不小于(0)的第一个可能(y)值就是:(y=0),所以，可以将(x=1,y=0)做为一组特解返回，也就是返回了一组“不小于零的贝祖数”。
((2))、当 (b≠0)时
(ecause gcd(a,b)=gcd(b,a\%b))
并且(① ax+by=gcd(a,b))
( herefore bx′+(a\%b)y′=gcd(a,b))
(ecause a−⌊a/b⌋∗b=a\%b)
( herefore bx′+(a−⌊a/b⌋∗b)y′=gcd(a,b))
变形一下：
(② ay′+b(x′−⌊a/b⌋∗y′)=gcd(a,b))
对比(① ②)系数：
( herefore) (x=y′,y=x′−⌊a/b⌋∗y′)
因此可以采取递归算法 先求出下一层的(x′)和(y′) 再利用上述公式回代即可
二、完整代码
#include <bits/stdc++.h>
using namespace std;
/**
* 功能：扩展欧几里得算法模板
* @param a 第一个数
* @param b 第二个数
* @param x 贝祖数x 最小非负整数
* @param y 贝祖数y 最小非负整数
* @return
*/
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() {
//优化输入
ios::sync_with_stdio(false);
int n;
cin >> n;
while (n--) {
int a, b;
cin >> a >> b;
int x, y;
exgcd(a, b, x, y);
printf("%d %d
", x, y);
}
return 0;
}