扩展欧几里得定理

现在我们已经知道了，方程ax+by=gcd（a，b） 的一组可行解一定有一组可行解，那么如何求解它喃？

而这个时候我们有一个方法可以帮助我们求解：

扩展欧几里得算法（Extended Euclidean algorithm, EXGCD），常用于求ax+by=gcd（a，b） 的一组可行解。

下面来看一下证明：

(没加载出来一定要多刷新一下，这渲染太慢了)

$$设 \begin{cases} ax1+by1=gcd(a,b)\\bx2+(a\ mod\ b)y2=gcd(b,a\ mod\ b) \end{cases} \\ ∵gcd(a,b)=gcd(b,a\ mod\ b);\\ ∴ax1+by1=gcd(b,a mod b)=bx2+(a\ mod\ b)y2;\\ 又∵a\ mod\ b=a-[\frac{a}{b}]*b\\ \begin{aligned} ∴bx2+(a\ mod\ b)y2&=bx2+(a-[\frac{a}{b}]*b)y2\\ &=bx2+ay2-[\frac{a}{b}]*b*y2\\ &=ay2+b(x2-[\frac{a}{b}]*y2)\\ &=ax1+by1\\ \end{aligned}\\ 由于对应项系数对应相等,所以 \\ \begin{cases} x1=y2\\ y1=x2-[\frac{a}{b}]*y2\\ \end{cases}$$

那么将x2，y2 不断代入递归求解直至gcd 为 0为止
在这之前有

$$gcd*x+0*y=gcd$$

，故x=1，y=0，再反过来带回去迭代便可以求出一组可行解

代码实现：

#include<bits/stdc++.h>
using namespace std;
int ex_gcd(int a,int b,int &x,int &y)//扩展欧几里得求ax+by=gcd（a，b）；
{
	if(!b){
		x=1;
        y=0;
		return a;
	}
	int gcd=ex_gcd(b,a%b,y,x);
	y-=a/b*x;
	return gcd;
}

int main()
{
    int a,b,x,y;
    cin>>a>>b;
    int gcd=ex_gcd(a,b,x,y); 
    printf("%dx+%dy=%d\n",a,b,gcd);
    cout<<"x="<<x<<" y="<<y<<endl;//方程的特解，可由线性代数相关知识推出通解；
    return 0;
}