扩展欧几里得算法求乘法逆元

本节需要前置知识扩展欧几里得算法和乘法逆元

在前面讲到乘法逆元中，我们推导出了逆元的一个比较简介的表示法

a\cdot a^{-1} \equiv 1 (mod \quad p)

这里的a^{-1}叫做a mod p的乘法逆元

上式不难写成

aa^{-1}=kp+1,k \in \mathbb{Z}

移项可以得到

aa^{-1} - kp = 1

上式的形式非常像扩展欧几里得算法所求的方程

ax+by=gcd(a, b)

而我们知道a mod p的乘法逆元存在的充要条件是a与p互质，即gcd(a,p)=1 所以我们令上式中a逆为x，-k为y，运用扩展欧几里得算法解方程

ax+ky=1

即可求得x为a mod p的乘法逆元

此方法求逆元没有快速幂求逆元中p必须为质数的条件，所以是更通用的方法

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// ax + by = gcd(a, b)
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(!b)
    {
        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);
    int n;
    scanf("%d", &n);
    while (n--)
    {
        ll a, p;//求a模p的乘法逆元
        scanf("%lld %lld", &a, &p);
        ll x, y;
        ll d = exgcd(a, p, x, y);
        if(d == 1)
        {
            printf("%lld\n", x);
        }else{
            puts("impossible");
        }
    }
    return 0;
}