AcWing 876. 快速幂求逆元

引入

费马小定理：若整数$a$, $p$ 互质且$p$是质数，则$a^{p-1}≡1(mod $ $p)$。

乘法逆元的定义：如果$ax≡1 (mod$ $p)$, 且 $gcd(a,p)=1$ ($a$与$p$互质)，则称$a$关于模 $p$ 的乘法逆元为 $x$。

思路

题目已经保证 $p$ 是质数。

（1）当$a$、$p$互质，且$p$为质数时，由费马小定理知 $a^{p-1}≡1(mod$ $p)$，则 $a*a^{p-2}≡1(mod$ $p)$，$a$的模$p$乘法逆元 $x=a^{p-2}$。

（2）当$a$、$p$不互质，且$p$为质数时，此时$a$一定是$p$的倍数，则$a*x≠1(mod$ $p)$，$a$的模$p$乘法逆元不存在 (或者由乘法逆元存在的充要条件也可知)。

这样，求$a$的模$p$乘法逆元就转换成用快速幂求$a^{p-2}$。

代码

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

typedef long long LL;

int qmi(int a, int k, int p)
{
    int res=1;
    while(k)
    {
        if(k&1) res=(LL)res*a%p;
        k>>=1;
        a=(LL)a*a%p;
    }
    return res;
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a, p;
        cin>>a>>p;
        if(a%p) cout<<qmi(a, p-2, p)<<endl;
        else puts("impossible");
    }

    return 0;
}