快速幂求逆元

​ 首先要了解乘法逆元的概念：

​ 给定三个正整数 $a,b,p$，如果满足：
$$ a·b \equiv1\mod p $$
​ 那么 $b$ 称为在 $\mod p$ 的条件下 $a$ 的乘法逆元，记作$a^{-1}$。

​ 注意：不是所有的数在某些模量下都有逆元。

​ $a$ 存在逆元的充要条件是 $a$ 与 $p$ 互质。
$$ \exists b\in \{x | x \in Z \land x \in[0,p - 1] \},a·b \equiv 1 \mod p \Leftrightarrow (a,p) = 1 $$

​ 同时我们又要了解一些求逆元所用的定理：

​ 欧拉定理：

​ 对于正整数 $a,p$ ，若 $(a, p) = 1$ （ $a$ 与 $p$ 互质）恒有：
$$ a ^ {\phi(p)} \equiv 1 \mod p $$

​ 根据这个定理，我们可以求出这个条件下 $a$ 的逆元：
$$ a^{\phi(p)} \equiv 1 \mod p $$

$$ a · a^{\phi(p) - 1} \equiv 1 \mod p $$

$$ [a ^ {-1}]_p = [a ^ {\phi(p) - 1}]_p $$

​ 特别的，费马小定理：如果 $p$ 为质数，那么 $\phi(p) = p - 1$，此时：
$$ [a ^ {-1}]_p = [a ^ {p - 2}]_p $$
代码

int inverse(int a, int p){
    return gcd(a, p) == 1 ? qmi(a, p - 2, p) : -1;
}

完整代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int gcd(int a, int b){
    return a % b ? gcd(b, a % b) : b;
}

int qmi(int a, int b, int p){

    int res = 1;

    while (b){
        if (b & 1) res = (ll) res * a % p;
        b >>= 1;
        a = (ll) a * a % p;
    }

    return res;
}

int inverse(int a, int p){
    return gcd(a, p) == 1 ? qmi(a, p - 2, p) : -1;
}

int main(){
    int t;
    cin >> t;
    while (t -- ){
        int a, p;
        cin >> a >> p;

        int ans = inverse(a, p);
        if ( ~ ans) cout << ans;
        else cout << "impossible";
        cout << endl;
    }

    return 0;
}