【算法】数论---乘法逆元

乘法逆元的定义

若整数 $b，m$ 互质，并且对于任意的整数 $a$，如果满足 $b|a$，则存在一个整数 $x$，使得 $\frac{a}{b}\equiv a\times x(\mathrm{mod}m)$ ，则称 $x$ 为 $b$ 的模 $m$ 乘法逆元，记为 $b^{-1}(\mathrm{mod}m)$。

$b$ 存在乘法逆元的充要条件是 $b$ 与模数 $m$ 互质。在 $b$ 与模数 $m$ 互质的基础上，当模数 $m$ 为质数时，$b^{m-2}$ 即为 $b$ 的其中一个乘法逆元（这是由费马小定理得出的结论），并且因为一个数的所有乘法逆元在模 模数$m$ 意义下是同余的,所以 $b^{m-2}modm$ 也是 $b$ 的其中一个乘法逆元。

费马小定理的定义

若 p 为质数，$\gcd (a,p)=1$，则 $a^{p-1}\equiv 1(\mathrm{mod}p)$。

如何求乘法逆元?

①：当 $\gcd (a,p)=1$，并且 p 为质数时，可以通过 快速幂+费马小定理 求逆元

例题：
给定 $n$ 组 $a_i,p_i$，其中 $p_i$ 是质数，求 $a_i$ 模 $p_i$ 的乘法逆元，若逆元不存在则输出 impossible。

注意：请返回在 $0\sim p-1$ 之间的逆元。

输入格式

第一行包含整数 $n$。

接下来 $n$ 行，每行包含一个数组 $a_i,p_i$，数据保证 $p_i$ 是质数。

输出格式

输出共 $n$ 行，每组数据输出一个结果，每个结果占一行。

若 $a_i$ 模 $p_i$ 的乘法逆元存在，则输出一个整数，表示逆元，否则输出 impossible。

数据范围

$1\le n\le 10^5$,
$1\le a_i,p_i\le 2\ast 10^9$

输入样例：

3
4 3
8 5
6 3

输出样例：

1
2
impossible

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
const int N = 100010;

LL power(LL a, LL b, LL p)  //快速幂
{
    LL ans=1 % p;
    for(;b;b>>=1)
    {
        if(b&1)ans=ans*a%p;
        a=a*a%p;
    }
    return ans;
}

void solve()
{
    LL a,p; cin>>a>>p;
    if(a%p==0)cout<<"impossible"<<endl;  //只有当a是p的倍数时，a与p才不互质，此时a在mod p下的逆元不存在。
    else cout<<power(a,p-2,p)<<endl;  //因为p是质数嘛！所以当a不是p的倍数时，a与p互质，所以a在mod p下的逆元存在，
    //并且因为p为质数，并且可以确定其中一个逆元为a^(p-2)，但是这个逆元可能会非常的大，
    //于是我们可以输出与a^(p-2)等效的另外一个较小的逆元a^(p-2)%p (它也是a在mod p下的逆元)
}

int main()
{
    int t; cin>>t;
    while(t--)
    {
        solve();
    }

    return 0;
}

②：当 $\gcd (a,p)=1$，但是 p 不为质数 时，可以通过 扩展欧几里得算法 求逆元，即通过 扩展欧几里得算法 来求解 同余方程：$a\ast x\equiv 1(\mathrm{mod}p)$ 来求出 $a$ 在 $modp$ 下的乘法逆元 $x$ 。

因为 $a\ast x\equiv 1(\mathrm{mod}p)$ 等价于 $a\ast x+p\ast y=1$ ，所以可以通过 扩展欧几里得算法 来求解出 乘法逆元 $x$

扩展欧几里得算法模板：

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

乘法逆元的作用是什么？

有了乘法逆元，我们在计数类问题中即使遇到 $a/b$ 这样的除法算式，也可以先把 $a,b$ 各自对 $模数p$ 取模，再计算 $a\ast b^{-1}modp$ 作为最终的结果。当然，前提是必须保证 $b,p$ 互质（当 $p$ 是质数时，等价于 $b$ 不是 $p$ 的倍数）