浅谈乘法逆元的线性算法

朴灿烈づ我的快乐病毒、 2021-12-12 09:09 227阅读 0赞

众所周知，乘法逆元可以通过Exgcd和费马小定理求解，如果我们在题目中需要预处理连续的一段数的逆元，我们需要更高效的算法求解。

**1.线性递推求解乘法逆元**

首先，我们声明在下列计算中同余均是在模p意义下

我们可以简单计算1\-1≡1

考虑任意正整数i，假定i-1的逆元已经正确计算，我们递推方程的计算过程如下：

![1625211-20190626171452079-2064759300.png][]

注意：最后一步我们在等号右边加p，目的是防止出现负数。由于p mod p =0 所以我们在右边加p是正确的

综上，我们得到了线性递推乘法逆元的算法。时间复杂度为O(n)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 int n, a[3000010], p;
     5 int main() {
     6     scanf("%d%d", &n, &p);
     7     a[1] = 1;
     8     for(register int i = 2; i <= n; ++i)
     9         a[i] =(ll) (p - p / i) * a[p % i] % p;
    10     for(register int i = 1; i <= n; ++i) printf("%d\n", a[i]);
    11     return 0;
    12 }

**2.阶乘逆元的线性递推**

![1625211-20190626172731515-904514282.png][]

我们先用Exgcd求出一个阶乘值的逆元

之后，我们就能轻松用递推求出阶乘的逆元了。

转载于:https://www.cnblogs.com/shl-blog/p/11091256.html

[1625211-20190626171452079-2064759300.png]: /images/20211211/115e5a9a3314452ab537f11592012057.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211211/349a796029514ac49dc2ed0bce4d4dbe.png
[1625211-20190626172731515-904514282.png]: /images/20211211/77af40cfe59946c8a4e3ce15f157a159.png

发表评论取消回复

表情：

评论列表（有 0 条评论，227人围观）

还没有评论，来说两句吧...

相关阅读

相关乘法逆元整理

乘法逆元 1.费马小定理 > 如果 $ a,p $ 互质，那么 $ a^\{p-1\} ≡ 1(mod p) $ > 又由逆元方程知 $ a\*x ≡ ...

约定不等于承诺〃/ 2024年04月20日 10:25/ 0 赞/ 38 阅读

相关线性求逆元

线性求逆元求1~n在%mod意义下的逆元 ![1735240-20190814082511164-1340216219.png][] mi[1]=1;

以你之姓@/ 2023年08月17日 15:35/ 0 赞/ 77 阅读

相关【算法与数据结构】——乘法逆元

定义若在mod p意义下，对于一个整数a，有a\b≡1(mod p)，那么这个整数b即为a的乘法逆元，同时a也为b的乘法逆元一个数有逆元的充分必要条件是gcd(

落日映苍穹つ/ 2022年09月04日 04:53/ 0 赞/ 128 阅读

相关（ACM数论）求乘法逆元的各种姿势~

首先，通过下面的式子来看看什么是乘法逆元~ x \ n % P = 1，其中x和P为已知且互素，n未知（比如在 2 \ n % 7 = 1 这个式子里，n就是乘法逆元）弄

太过爱你忘了你带给我的痛/ 2022年07月17日 03:24/ 0 赞/ 174 阅读

相关 51nod 1256 乘法逆元（exgcd）

题目链接： [点击打开题目链接][Link 1] 题解： K∗MmodN=1等价于 K∗M=N∗X\+1。即 K∗M\+N∗(−X)=1。可以用扩展欧几里德，求

柔光的暖阳◎/ 2022年06月15日 02:36/ 0 赞/ 193 阅读

相关详解--乘法逆元

今天我们来探讨逆元在ACM-ICPC竞赛中的应用，逆元是一个很重要的概念，必须学会使用它。对于正整数![20140613102654328][]和![20140613

怼烎@/ 2022年06月11日 07:48/ 0 赞/ 319 阅读

相关乘法逆元 51Nod - 1256——同余定理+逆元(乘法逆元) (拓展欧几里得算法求逆元)

给出2个数M和N(M < N)，且M与N互质，找出一个数K满足0 < K < N且K \ M % N = 1，如果有多个满足条件的，输出最小的。 Input 输入2个数

比眉伴天荒/ 2022年05月19日 13:41/ 0 赞/ 222 阅读

相关乘法逆元的几种计算方法

转载自：[https://blog.csdn.net/rain722/article/details/53170288][https_blog.csdn.net_rain722

Bertha 。/ 2022年03月10日 13:28/ 0 赞/ 319 阅读

相关浅谈乘法逆元的线性算法

众所周知，乘法逆元可以通过Exgcd和费马小定理求解，如果我们在题目中需要预处理连续的一段数的逆元，我们需要更高效的算法求解。 1.线性递推求解乘法逆元首先，我们声明在下

朴灿烈づ我的快乐病毒、/ 2021年12月12日 09:09/ 0 赞/ 228 阅读

相关乘法逆元的求法（5种）

若a\b≡1（mod p）即a，b互为mod p意义下的逆元即（x/a）%p应为x\b%p 一、扩展欧几里得求逆元根据a\b+p\k=1 板子O(logN)

╰半橙微兮°/ 2021年11月02日 09:46/ 0 赞/ 761 阅读