Exgcd扩展欧几里得

using namespace std;
const int N = 1000003, null = INT64_MAX;
typedef long long ll;
ll m,x,y;
bool f[N];
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
		x=1;y=0;
		return a;
	}
	ll d=exgcd(b,a%b,y,x);
	 y-=a/b*x;
	 return d;	
}

int main() {
	   
	   int a,b;
	   cin>>a>>b;
	   ll d= exgcd(a,b,x,y);
	   cout<<x+b/d*1;
	      
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

求解ax+by=c;

• x=x0-b/d*k
• y=y0+b/d*k