原题：
求关于xx的同余方程ax≡1(mod b)的最小正整数解。
裸题
当年被这题劝退，现在老子终于学会exgcd了哈哈哈哈哈哈哈哈
ax≡1(mod b) => ax=1+by => ax-by=1 => ax+by=1
若要保证有解，必须满足gcd(a, b)|1即gcd(a, b)=1
那么exgcd搞完之后只需加减b就能得到最小非负整数解
注意这里不是在解出y<0的情况下让x=-x
因为这里符号变化的是b，也就是说如果要求输出y，那么y应该等于-y
而跟x没有什么关系
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 #define LL long long 8 LL exgcd(LL a,LL b,LL &x,LL &y){ 9 if(!b){ x=1,y=0; return a;} 10 LL d=exgcd(b,a%b,x,y); 11 LL _x=x,_y=y; 12 y=_x-(a/b)*_y,x=_y; 13 return d; 14 } 15 LL a,b; 16 int main(){ 17 //freopen("ddd.in","r",stdin); 18 cin>>a>>b; 19 LL x,y,d; 20 d=exgcd(a,b,x,y); 21 //if(y<0) x=-x; 22 x=(x%b+b)%b; 23 cout<<x<<endl; 24 return 0; 25 }
原文：https://www.cnblogs.com/cdcq/p/11629714.html
