[C++知识库] c++乘法逆元

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> c++乘法逆元 -> 正文阅读

[C++知识库]c++乘法逆元

逆元是什么

我们都知道，在模意义下：

$(a+b)\%p=(a\%p+b\%p)\%p$

$(a-b)\%p=(a\%p-b\%p)\%p$

$(a\times b)\%p=(a\%p\times b\%p)\%p$

但是：

$(\dfrac{a}{b})\%p\neq (\dfrac{a\%p}{b\%p})\%p$

因此，逆元就诞生了。

若 $ax\equiv 1 \pmod p$ ，那么我们称 $x$ 为 $a$ 关于 $p$ 的逆元，用 $a^{-1}$ 表示

所以 $(\dfrac{a}{b})\%p=(a\%p\times b^{-1}\%p)\%p$

这样我们就可以解决除法的问题了。

怎么求逆元

求逆元的前提： $\gcd(a,p)=1$

费马小定理

因为 $a^p\equiv a\pmod p$ ，

所以 $a^{p-2}\equiv a^{-1} \pmod p$

所以 $a^{-1}\equiv a^{p-2} \pmod p$

具体证明参见OI-WIKI

时间复杂度为 $\ p)$

扩展欧几里德

$a x + p y = 1$ 的一组解 $(x, y)$ ， $x$ 是 $a$ 关于 $p$ 的逆元。

证明：

$\begin{aligned} ax+py &= 1 \\ ax\%p+py\%p &= 1\% p \\ ax+py &\equiv 1\pmod p \\ ax &\equiv 1 \pmod p \end{aligned}$

所以 $x$ 是 $a$ 关于 $p$ 的逆元。时间复杂度为 $\ p)$

连续数的逆元

求 $1$ 到 $n$ 的逆元，如果一个一个求，那么很容易超时。我们可以线性来求。

显然， $1^{-1}\equiv 1\pmod p$

假设现在我们求完了前 $i ? 1$ 个数的逆元，要求第 $i$ 个。我们令 $k=\lfloor\frac{p}{i}\rfloor,j=p \% i$ ，有 $p = ki + j$ ，所以

$ki+j\equiv \pmod p$

两边同时乘 $i^{-1}\times j^{-1}$ 得：

$kj^{-1}+i^{-1}\equiv 0 \pmod p$

$i^{-1}\equiv -kj^{-1} \pmod p$

将 $k=\lfloor\frac{p}{i}\rfloor,j=p \% i$ 代入得：

$i^{-1}\equiv -\lfloor\frac{p}{i}\rfloor\times(p \% i)^{-1} \pmod p$

因为 $p\% i<i$ ，我们已经求出小于 $i$ 的正整数的逆元了，所以 $j$ 的逆元已知。

于是，当 $i > 1$ 时， $i^{-1}\equiv -\lfloor\frac{p}{i}\rfloor(p\% i)^{-1} \pmod p$

code

ny[1]=1;
for(int i=2;i<=n;i++){
	ny[i]=(p-p/i)*ny[p%i]%p;
}

求阶乘的逆元

求 $1$ 到 $n$ 的逆元。同样地，我们也可以用线性的方法来求。

先求出 $1$ 到 $n$ 的阶乘 $s [i]$ ，然后用 $\ p)$ 的时间复杂度求出 $s [n]$ 的逆元 $n y [n]$

对于每一个 $i(1\leq i<n)$ ，因为 $\dfrac{1}{i!}=\dfrac{1}{(i+1)!}*(i+1)$ ，所以 $ny[i]=ny[i+1]*(i+1)\%p$

时间复杂度 $\ p)$

code

jc[0]=1;
for(int i=1;i<=n;i++){
	jc[i]=jc[i-1]*i%p;
}
ny[n]=mi(jc[n],p-2);
for(int i=n-1;i>=0;i--){
	ny[i]=ny[i+1]*(i+1)%p;
}

其中 $mi$ 是求快速幂

求任意n各数的逆元

先计算出前缀积 $s [i]$ ，再求 $s [n]$ 的逆元 $n y [n]$

与求阶乘的逆元类似，对于每一个 $i(1\leq i<n)$ ， $ny[i]=ny[i+1]*a[i+1]\% p$

那么 $a [i]$ 的逆元就是 $s[i-1]*ny[i]\%p$ ，时间复杂度也是 $\ p)$

C++知识库最新文章

【C++】友元、嵌套类、异常、RTTI、类型转换

通讯录的思路与实现（C语言)

C++PrimerPlus 第七章函数-C++的编程模块（

Problem C: 算法9-9~9-12：平衡二叉树的基本

【C语言】以深厚地基筑伟岸高楼-基础篇（六

c语言常见错误合集

加:2022-10-08 20:22:12 更:2022-10-08 20:26:50

360图书馆购物三丰科技阅读网日历万年历 2024年5日历

-2024/5/19 7:51:41-

图片自动播放器
↓图片自动播放器↓

TxT小说阅读器
↓语音阅读,小说下载,古典文学↓

一键清除垃圾
↓轻轻一点,清除系统垃圾↓

图片批量下载器
↓批量下载图片,美女图库↓

网站联系: qq:121756557 email:121756557@qq.com IT数码