引入一个定理：Bezout定理

对于任意整数 $a,b$ 存在一对整数$x,y$,满足$ax+by=gcd(a,b)$

证明：

在欧几里得算法的最后一步，即$b=0$时，显然有一对整数，$x=1,y=0$ ,满足$ax+by=a*1+b*0=gcd(a,0)$

若$B>0$ 则$gcd(a,b)=gcd(b,a mod b)$.

假设存在一对整数$x,y$,满足$b*x+(a mod b) * y=gcd(b,a mod b)$ ,因为$b*x+(a mod b)*y=b*x+(a-(a/b)*b)*y=a*y+b*(x+(a/b)*y)$ 所以令$x'=y,y'=(x+(a/b)*y)$

此时的$x',y'$便满足$a*x'+b*y'=gcd（a,b）$ 逆推即可得到一组特解

将$a$ 变成最小正整数便得出答案

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll a,b,x,y;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0){
		x=1,y=0;
		return a;
	} 
	ll ans=exgcd(b,a%b,x,y);
	ll z=x;
	x=y;
	y=(z-y*(a/b));
	return ans;
	
} 
int main()
{
	scanf("%d%d",&a,&b);
	exgcd(a,b,x,y);
	cout<<(x % b + b) % b;
 } 

同余模方程ax=b(mod n)或ax+ny=b。 分析，设a和n的gcd（a,n）则ax+ny=b等价于a'x+n'y=b/gcd(a,n)。 则此方程有gcd(a,n)个解且当且仅当b能被gcd(a,n)整除时有解 其中第一个解为x0=x(n/d)%n。 第d-1个解为xi=(x0+i*(n/d))%n(1<=i<=d-1) 那么我们如何求解？ 那么我们先来看第一个式子ax+by=gcd(a,b) 将a,b代换为b与a%b(欧几里得算法） 则bx'+(a%b)y'=gcd(b,a%b) 显然由欧几里得定理可知gcd(a,b)=gcd(b,a%b) 则原式:ax+by=bx'+(a%b)y'=bx'+(a-a/bb)y'=ay'+b(x'-a/by') 则由恒等可知x=y',y=x'-a/b*y' 发现了什么？ 我们可以用递归求解了！并且边界是b=0，此时 x=1,y=0 不过我们第一次求出的不一定是最小整数解 那么我们在处理下就行了

代码如下

#include<bits/stdc++.h>
using namespace std;
int a,b,x,y;
void exgcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1;y=0;
		return;
	}
	int xl,yl;
	exgcd(b,a%b,xl,yl);
	x=yl;
	y=xl-(a/b)*yl;
}
int main()
{
	cin>>a>>b;
    exgcd(a,b,x,y);
    cout<<(x+b)%b;
    return 0;
}