877. 扩展欧几里得算法 · znzryb

## 思路讲解

因为（a, b）= (b, a mod b) 【（）表示最大公约数】

![image](https://media.znzryb.com/20241203-9d3ab3c5/image_57a6c18a.png)

![image](https://media.znzryb.com/20241203-9d3ab3c5/image_c3d1032b.png)

## AC代码

也可以这么写

```cpp
void Exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) x = 1, y = 0;
    else Exgcd(b, a % b, y, x), y -= a / b * x;
}
```

[https://www.acwing.com/problem/content/submission/879/](https://www.acwing.com/problem/content/submission/879/)

```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,T;

ll exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		// ax+by=(a,b)
		// b=0,
		x=1,y=0;
		return a;
	}
	ll d=exgcd(b, a%b, y, x);
	y-=(a/b)*x;
	return d;
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		ll a,b,x,y;
		cin>>a>>b;
		exgcd(a, b, x, y);
		cout<<x<<" "<<y<<endl;
	}
	return 0;
}
// AC https://www.acwing.com/problem/content/submission/879/
```

## 心路历程（WA，TLE，MLE……）