当前位置 : 主页 > 编程语言 > 其它开发 >

乘法逆元学习笔记

来源:互联网 收集:自由互联 发布时间:2022-05-30
乘法逆元和求法 基本的数论知识,有必要补一发。 开始之前 模运算:取余运算,比如 \(a \bmod b\) 就是 \(a\) 除以 \(b\) 得到的余数。 性质:在加、减、乘、乘方的运算过程中,进行取余
乘法逆元和求法

基本的数论知识,有必要补一发。

开始之前
  • 模运算:取余运算,比如 \(a \bmod b\) 就是 \(a\) 除以 \(b\) 得到的余数。

  • 性质:在加、减、乘、乘方的运算过程中,进行取余运算,不会对结果产生影响。

  • 优先级:取余运算的优先级和乘法、除法的优先级相同,高于加减法的优先级。

  • 互质:表示两个数的最大公约数为 \(1\),表示为 \((x,y)=1\)

  • 同余(这个比较重要): 对于整数 \(m\),如果整数 \(a,b\) 满足 \((a-b) \bmod m=0\),即 \((a-b) \div m\) 得到的是一个整数值,则称整数 \(a\)\(b\) 对模 \(m\) 同余,记作 \(a\equiv b \pmod{m}\)

  • 同余的性质:自反性、对称性、传递性、同加性、同乘性、同幂性等。

    • 自反性:\(a \equiv a \pmod{p}\)
    • 对称性:如果 \(a \equiv b \pmod{p}\),则有 \(b \equiv a \pmod{p}\)
    • 传递性:如果 $a \equiv b \pmod{p} \ $ 且 \(\ b \equiv c \pmod{p}\),则有 \(a \equiv c \pmod{p}\)
    • 同加性:如果 \(a \equiv b \pmod{p}\) 则有 \(a + c \equiv b + c \pmod{p}\)
    • 同乘性:如果 $a \equiv b \pmod{p} \ $,则 \(\ a \times c \equiv b \times c \pmod{p}\)
      \(\qquad \ \ \, \,\) 如果 \(a \equiv b \pmod{p}\)\(c \equiv d \pmod{p}\) 则有 \(a \times c \equiv b \times d \pmod{p}\)
    • 同幂性:如果 \(a \equiv b \pmod{p}\) 则有 \(a^n \equiv b^n \pmod{p}\)
问题背景

求解 \(\dfrac{a}{b} \bmod p\) 的值,因为不能先对 \(a,b\) 取模再相除,所以引入了逆元

逆元可以理解为 \(\bmod p\) 意义下 \(b\) 的倒数。
假设 \(inv_b\)\(b\) 的逆元,则有 $$inv_b \times b \equiv 1 \pmod{p}$$
\(\left( inv_b -1 \right) \bmod p =0\)

性质 第一个性质

\[\dfrac{a}{b} \equiv a \times inv_b \pmod{p} \]

证明:

\[\because b \times inv_b \equiv 1 \pmod{p} \]

\[\therefore \left( b \times inv_b -1 \right) \bmod p =0 \]

\[\because x \bmod p= x \times y \bmod p \]

\[\therefore \dfrac{a}{b} \times (b \times inv_b -1) \bmod p =0 \]

\[\therefore (a \times inv_b - \dfrac{a}{b}) \bmod p =0 \]

\[\therefore \dfrac{a}{b} \equiv a \times inv_b \pmod{p} \]

得证。

唯一性 性质

每个数的逆元唯一。

证明

假设 \(b\) 有两个逆元 \(x,y\)
则可知 \(a \times x \equiv a \times y \pmod{p}\)

\[\therefore \left(a \times \left( x - y \right) \right) \bmod p =0 \]

\[\because a \bmod p \ne 0 \]

\[\therefore x=y \]

所以每个数的逆元唯一

逆元求法: 快速幂

这个做法的基础是费马小定理

\(p\) 为质数,\(a\) 为正数,且 \((a,p)=1\),则有 \(a^{p-1} \equiv 1 \pmod{p}\)

根据逆元的定义 \(inv_a \times a \equiv 1 \pmod{p}\) 可知:$$\because inv_a \times a \equiv a^{p-1} \pmod{p}$$

\[\therefore inv_a \equiv a^{p-2} \pmod{p} \]

也就是说,一个数 \(i\) 在模 \(p\) 意义下的逆元就是 \(i^{p-2} \bmod p\)
用快速幂计算即可。

int x,p;
int ksm(int a,int b){int s=1,t=a;while(b){if(b&1)s=(s*t)%p;t=(t*t)%p;b>>=1;}return s;}
int main(){cin>>x>>p;cout<<ksm(x,p-2)<<endl;}
线性求逆元

也就是Luogu P3811【模板】 乘法逆元

对于一个数 \(k\),找到一个 \(inv_k\) 使得 \(k \times inv_k \equiv 1 \pmod{p},k \in \left[ 1,n \right]\)

首先,设 $$p=a \times k + b,b \times inv_b \equiv 1 \pmod{p}$$
\(b\) 给换掉: $$(p - a \times k) \times inv_b \equiv 1 \pmod{p}$$
通过乘法分配率可以得到: $$p \times inv_b - a \times k \times inv_b \equiv 1 \pmod{p}$$
因为 \(p \times inv_b\) 里面有 \(p\) 这一项,所以可以直接消掉,得到: $$- a \times k \times inv_b \equiv 1 \pmod{p}$$
\(a,b\) 都用 \(k,p\) 表示可得: $$- \ \left\lfloor\dfrac{p}{k}\right\rfloor \times k \times inv_{p \ \bmod k} \equiv 1 \pmod{p}$$
因为 \(k \times inv_k \equiv 1 \pmod{p}\),且同余具有同乘性,所以左右同乘 \(inv_k\) 可得 $$- \left\lfloor\dfrac{p}{k}\right\rfloor \times inv_{p \bmod k} \equiv inv_k \pmod{p}$$
有个负号,而左边加上 \(p \times inv_{p \bmod k}\) 对结果无影响同时能消掉负号:$$\left(p- \left\lfloor\dfrac{p}{k}\right\rfloor \right) \times inv_{p \bmod k} \equiv inv_k \pmod{p}$$
得出结论:设 \(inv_i\)\(i\) 的逆元,则有递推式: $$inv_i \equiv \left(p- \left\lfloor\dfrac{p}{i}\right\rfloor \right) \times inv_{p \bmod i} \pmod{p}$$
写成代码就是: for(int i=2;i<=n;i++)ans[i]=(p-p/i)*ans[p%i]%p;
code:

#include <bits/stdc++.h>
#define int long long
using namespace std;int ans[6000000],n,p;
signed main(){
	cin>>n>>p;ans[1]=1;/*初始化*/
	for(int i=2;i<=n;i++)ans[i]=(p-p/i)*ans[p%i]%p;/*线性求逆元*/
	for(int i=1;i<=n;i++)cout<<ans[i]<<endl;return 0;
}
上一篇:【转】数据库连接池到底应该设多大
下一篇:没有了
网友评论