ps:自用，自己看着方便留着的记录，部分定理直接引用详细证明没有写。
扩展欧几里得算法
找出一对整数((x,y))使得 (ax+by=gcd(a,b)) 假设(a>=b)
代码：版本一
void exgcd(int a,int b,int &d,int &x,int &y){
if(!b){d=a,x=1,y=0;}
else {exgcd(b,a%b,d,y,x);y-=(a/b)*x;}
}
代码：版本二
int exgcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,x,y),t=x;
x=y,y=t-a/b*y;
return d;
}
证明：
-
当(b=0)时，(x=1，y=0)成立
-
(ax+by=gcd(a,b)=gcd(b,a\,Mod\,b)=bx’+(a\,Mod\,b)y’)
(ax+by=bx'+(a\,Mod\,b)y'=bx'+(a-lfloor{a/b} floor *b)y')
(ax+by=ay'+b(x'-lfloor{a/b floor}*y'))
整理可得
[egin{cases} x=y'\ y=x'-lfloor a/b floor *y' end{cases} ]
其中(x'\,y')是方程进一步转换后的结果，一直计算到(b=0)时即可得出解，此时回代即可。
而(x,\,y)可由(x',y')得出则可以参考贝祖定理。
贝祖定理（裴蜀定理）
在数论中，裴蜀定理是一个关于最大公约数（或最大公约式）的定理，裴蜀定理得名于法国数学家艾蒂安·裴蜀。
裴蜀定理说明了对任何整数 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.
有代码得出的(x,y)为方程的其中一组解，如果记为(x_0,y_0)后可推导出通解为
[egin{cases}
x=x_0+k*b\
y=y_0-k*a\
k∈Z
end{cases}
]
而对于(ax+by=t（其中t为gcd（a,b）的倍数）)的解则是在(x_0,y_0)的基础上乘上相应的倍数。