同余模方程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;
}