洛谷 P1082 [NOIP2012 提高组] 同余方程
题意
求解(ax equiv 1 mod b)
套路变形为(ax-by=1)
题目保证有解（即为a、b互质），使用exgcd求解
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
int exgcd(int A,int B,int &x,int &y){
if(B==0) return x=1,y=0,A;
int g=exgcd(B,A%B,x,y);
int t=x;
x=y;y=t-A/B*y;
return g;
}
signed main(){
cin>>a>>b;
int x,y;
int g=exgcd(a,b,x,y);
int stp=b/g;
if(stp<0) stp=-stp;
x%=stp;
if(x<=0) x+=stp;
cout<<x<<endl;
return 0;
}