快速幂求乘法逆元

在介绍快速幂求乘法逆元之前先了解费马小定理:
如果p是质数，且a不是p的倍数，则

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

这个定理在数论方面有着重要应用

首先给出逆元的定义
对于整数b,如果

\exist x \in Z,使得 \forall a \in Z:\\
有\frac{a}{b} \equiv ax (mod \quad p)

则称x为b mod p的乘法逆元
上述概念可能有些绕，而一个感性理解逆元的方法就是，逆元将除法转变成乘法
也就是说，当一个数要除以b时，我们可以求得一个x，使得在mod p条件下除以b的结果与乘x的相同。注意，上述式子中除数是任意整数

b的乘法逆元记作

b^{-1}

读作b逆，注意和1/b不是一个东西

b mod p的乘法逆元存在的充要条件是b与p互质

在上式中两侧同时乘b可得

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

此时的形式和上述费马小定理一致，可以得到

b ^ {p - 1} \equiv 1(mod \quad p) \\
b b ^{p-2} \equiv 1(mod \quad p) \\
b^{-1}=b^{p-2}

注意费马小定理的条件，p必须是质数，且b不能为p的倍数

所以乘法逆元的问题被转化为了简单形式的快速幂
上代码

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

ll qmi(ll a, ll k, ll m)//快速幂模板
{
    //a ^ k % m
    ll res = 1;
    while (k)
    {
        if(k & 1)   res = res * a % m;
        k >>= 1;
        a = a * a % m;
    }
    return res;
}

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 res = qmi(a, p - 2, p);
        if(a % p)
            printf("%lld\n", res);
        else
            puts("impossible");
    }
    return 0;
}