乘法逆元

• 0. 概述
• 1. 板子
• 2. 性质
• 3. 线性求逆元板子

0. 概述

• 同余式：如果 $a,b$ 模 $m$ 的余数相同，则称 $a,b$ 模 $m$ 同余，记为 $a\equiv b$，例如：$8 \equiv 2\ (mod\ 3)$

• 乘法逆元：若 $a,b$ 互质，且满足同余方程 $ax\equiv 1\ (mod \ b)$，则称 $x$ 为 $a\ mod \ b$ 的乘法逆元，记作 $a^{-1}$，例如：$8x \equiv 1\ (mod\ 5)$，解得 $x=2,7,12…$

• 费马小定理：若 $p$ 为质数，且 $a,p$ 互质，则 $a^{p-1}\equiv1\ (mod\ p)$，例如：$4^{3-1}\equiv 1(mod\ 3)$

• 费马小定理求乘法逆元：$a^{p-1}\equiv1\ (mod\ p)$，得 $a×a^{p-2}\equiv 1\ (mod\ p)$，根据乘法逆元的定义，所以 $a^{p-2}$ 就是 $a$ 模 $p$ 的乘法逆元

1. 板子

// 幂取余,a^b%p
int qmi(ll a,int b,int p) {
    int res=1; // 累乘因子
    while(b) {
        if(b&1) res=res*a%p;
        a=a*a%p; // 提权
        b>>=1;
    }
    return res;
}

int main() {
    cin>>a>>p;
    // 快速幂计算a^(p-2),就是a%p的乘法逆元
    // 如果a,p互质,才有a%p乘法逆元
    if(a%p) {
        printf("%d\n",qmi(a,p-2,p));
    }
    return 0;
}

2. 性质

• $14/4\ (mod\ 5)=7/2 \ (mod\ 5)=7×3\ (mod\ 5)$，这是因为 $2×3\ mod\ 5=1$，也可以理解为 $3$ 和 $2$ 在模 $5$ 下互为倒数

• 求乘法逆元的方法：$2^{-1} \ mod\ 7$，模 $7$ 下 $2$ 的乘法逆元是，求谁乘以 $2$ 再模 $7$ 等于 $1$，很容易口算得到 $4×2\ (mod\ 7)=1$

  • 通过费马小定理计算，$a^{p-2}$ 即 $2^{7-2}=32$
  • 模 $n$ 下互为乘法逆元，一般只考虑比 $n$ 小的，所以 $32$ 对 $7$ 取模得到 $4$，那么模 $7$ 下 $2$ 的乘法逆元是 $4$

• $a$ 在模 $n$ 内的乘法逆元 $a^{-1}\ (1<=a^{-1}<n)$ 是唯一的，比如模 $5$ 下 $2$ 和 $3$ 互为乘法逆元，除此外再无别的逆元

• $1$ 不管模谁都是余 $1$

• $a$ 的乘法逆元的乘法逆元是 $a$，$z=a^{-1},\ z^{-1}=(a^{-1})^{-1}=a$

• 什么时候用乘法逆元？当题目中推导出来的公式带有除法，并且要让结果对某个数作模运算时，应用乘法逆元把除法变为乘法，一直除再作模运算是会出错的，可以这样想，加减乘都是从低位起开始运算，只有除法是从高位开始运算，而模运算又是取低几位，所以应该把除法转换为乘法

3. 线性求逆元板子

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=3e6+6;
// 给定n,p,计算1~n中所有整数在模p意义下的乘法逆元
// a模p的乘法逆元定义为 a*a_inv等价于1(mod p),去找a_inv是多少
// 线性求逆元
int inv[maxn]; // 存储每个数字的逆元

signed main() {
	int n,p;
	cin>>n>>p; // n是范围,p是模数
	inv[1]=1; // 1的逆元是1, (1*1)mod p=1
	cout<<inv[1]<<'\n';
	for(int i=2;i<=n;i++) {
		inv[i]=-(p/i)*inv[p%i]; // x_inv=-k*r_inv (怎么推导的···看b站视频吧)
		inv[i]=(inv[i]%p+p)%p; // 防止负数产生
		cout<<inv[i]<<'\n';
	}
	return 0;
}

打赏