扩展欧几里得算法

$(a,b)=(b,a \mod b)=d$

$yb+x(a \mod b)=d$

$yb+ax-y/b*bx=d$

$ax+b(y-a/b*x)=d$

所以在交换以后，$x_1=x,y_1=y-y/b*x$

代码实现

#include<bits/stdc++.h>
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);
	//by+x(a-a/b*b)=d;
	//ax+b(y-a/b*x)=d
	
	//x=x y=y-a/b*x;
	
	y=y-a/b*x;
	return d;
}
int main()
{
	int a,b;
	cin>>a>>b;
	int x,y;
	exgcd(a,b,x,y);
	cout<<(x%b+b)%b<<endl;
	return 0;
}