扩展欧几里得算法

​ 给定一对正整数 $a,b$，求出一组 $x,y$，使其满足：
$$ a · x + b · y = (a, b) $$

贝祖定理：

​ 有一个线性不定方程
$$ ax+by=c $$
​ 若此方程有解，那么
$$ c=k·(a,b) , k \in Z^+ $$

​ 如何求解这个线性不定方程：

​ 我们知道最大公因数的求解方法，所以这个方程可以写成如下形式：
$$ ax+by=(a,b)=(b, a\%b)=bx’+a\%by’\\ $$
$$ a\%b=a-\lfloor\frac{a}{b}\rfloor·b\\ $$
$$ ax+by=bx’+(a-\lfloor\frac{a}{b}\rfloor·b)y’\\ $$
$$ ax+by=ay’+b·(x’-\lfloor\frac{a}{b}\rfloor·y’) $$
​ 对比系数，可得：
$$ x=y’\\ $$
$$ y=x’-\lfloor\frac{a}{b}\rfloor·y’ $$
​ 由此可知，我们可以通过递归的思想来求出符合的一组解。

​ 递归边界：当 $b = 0$ 时，$(a,b)=a,x=1,y\in Z$

​ 特别的，用扩展欧几里得算法还可以求出乘法逆元。
$$ ax\equiv 1 \mod p\\ $$
$$ ax+py=1 $$
​ 当且仅当 $(a,p) = 1$ 时有解。

代码

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

用扩展欧几里得算法求乘法逆元 完整代码

#include <bits/stdc++.h>
#define int long long 

using namespace std;

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

int mod(int a, int p){
    return (a % p + p) % p;
}

main(){
    int t;
    cin >> t;
    while (t -- ){
        int a, p;
        cin >> a >> p;
        int x, y;
        int d = exgcd(a, p, x, y);
        if (d == 1) cout << mod(x, p);
        else cout << "impossible";
        cout << endl;
    }

    return 0;
}