> For the complete documentation index, see [llms.txt](https://wandersofb.gitbook.io/blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wandersofb.gitbook.io/blog/suan-fa/shu-xue/kuo-zhan-ou-ji-li-de.md).

# 扩展欧几里得

**贝祖等式**

给定两个整数 $$a,b$$，必存在整数 $$x,y$$ 使得 $$ax + by = c$$ 且 $$gcd(a,b)|c$$。

**算法分析**

因为

$$
gcd(a,b) = gcd(b,a%b)
$$

可得

$$
bx^{'} + (a - \lfloor a / b \rfloor \* b)y^{'} = gcd(b, a%b)
$$

继而

$$
ay^{'} + b(x^{'} - \lfloor a / b \rfloor \* y^{'}) = gcd(b,a%b) = gcd(a,b)
$$

故而

$$
x = y^{'},y = x^{'} - \lfloor a / b \rfloor \* y^{'}
$$

```cpp
#include<iostream>
#include<algorithm>
using namespace std;

void exgcd(int a, int b, int &x, int &y){
    if (!b){
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
    return;
}

int main(){
    int n; cin >> n;
    while (n -- ){
        int a, b, x, y; cin >> a >> b;
        exgcd(a, b, x, y);
        printf("%d %d\n", x, y);
    }
}
```

**时间复杂度分析**

* 这题的时间复杂度和欧几里得算法一样。欧几里得算法时间复杂度 $$O(\log b)$$，总时间复杂度 $$O(n \log b)$$。

**线性同余方程**

> 给定 $$n$$ 组数据 $$a\_i,b\_i,m\_i$$，对于每组数求出一个 $$x\_i$$，使其满足 $$a\_i\*x\_i\equiv b\_i\pmod m$$，如果无解则输出 `impossible`。

由

$$
a\_i\*x\_i\equiv b\_i\pmod m
$$

可得 $$\exists y \in Z$$

$$
ax = my + b \Rightarrow ax + my^{'} = b
$$

由之前的贝祖等式可知，只要 $$gcd(a,m)|b$$，我们就可以利用扩展欧几里得算法求解线性同余方程。

```cpp
#include<iostream>
#include<algorithm>

using namespace std;
void exgcd(int a, int b, int &x, int &y){
    if (!b){
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}


int main(){
    int n; cin >> n;
    while (n -- ){
        int a, b, m; cin >> a >> b >> m;
        int x, y;
        exgcd(a, m, x, y);
        int gcd = a * x + m * y;
        if (b % gcd == 0)
            cout << (long long)b / gcd * x % m << endl; 
        else 
            cout << "impossible" << endl;
    }
}
```