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

太过爱你忘了你带给我的痛 2022-07-17 03:24 154阅读 0赞

首先，通过下面的式子来看看什么是乘法逆元~

x \* n % P = 1，其中x和P为已知且互素，n未知（比如在 2 \* n % 7 = 1 这个式子里，n就是乘法逆元）

弄懂什么是乘法逆元，来看看有什么姿势可以把它求出来吧~

**姿势1.暴力（此姿势不要求P为素数）**

没有什么问题是一个暴力解决不了的，如果有，那就两个（手动滑稽）

代码如下：

int n;
    for(int i = 1 ;i <= P ;i++)
    {
        if(x * i % P == 1)
        {
            n = i;
            break;
        }
    }

**虽然暴力简单粗暴，但是它的时间复杂度为O(P)，只能在P较小的情况使用，局限性有点大。**

**姿势2.快速幂（此姿势要求P为素数）**

这个姿势是由费马巨巨的费马小定理（x^(P-1) ≡ 1 mod P）得来的：

x^(P-1) ≡ 1 mod P 即 x^(P-1) % P = 1
    
    已知 x * n % P = 1
    
    所以有 x * n % P = x^(P-1) % P 即 n % P = x^(P-2) % P

**到这里可以看出，逆元有无数个：n,n+P,n+2\*P,…**

一般情况下我们只要求那个最小的正整数，这样问题就转化为求 x^(P-2) % P

代码就不贴了，在网上找个有求模快速幂的模版，把x，P-2，P代进去就可以了

**这个姿势的时间复杂度为O(log P)，是个不错的姿势（手动滑稽）**

**姿势3.扩展欧几里德算法（此姿势不要求P为素数）**

首先，我们将式子变形一下~

x \* n % P = 1 等价于 n \* x + k \* P = 1，其中k为整数

因为 x 和 P 互素，所以 gcd (x ,P) = 1（最大公约数为1）

所以有 n \* x + k \* P = gcd (x ,P)

这样问题就转化为，求二元一次方程 n \* x + k \* P = gcd (x ,P) 的解

代码同样不贴了， 在网上找个扩展欧几里德的模版，把 x , P 代进去。

**不过要注意，算出来的n有可能是负数，也有可能不是最小的。若需要得到最小的正整数，加上如下代码即可：**

n = n % P;//处理不是最小的情况
    while(n < 0)//处理负数的情况
    {
        n =( n + P ) % P;
    }

**到这里可以得出结论：逆元的集合为｛…，n - 2 \* P，n - P，n , n + P，n + 2 \* P，… ｝**

**这个姿势的时间复杂度为O(log P)，是个不错的姿势（手动滑稽）**

发表评论取消回复

表情：

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

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

相关阅读

相关乘法逆元整理

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

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

相关线性求逆元

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

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

相关求乘法逆元的两种方法（费马小定理）（JAVA）

目录引入：分析：费马小定理求逆元（logn）代码：初始化1~n对p的逆元（N）

浅浅的花香味﹌/ 2023年01月10日 14:52/ 0 赞/ 98 阅读

相关数论-同余与逆元

文章目录同余一元线性同余方程逆元逆元与除法取模例题 HDU-5976 同余 -----------

曾经终败给现在/ 2022年11月25日 14:30/ 0 赞/ 128 阅读

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

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

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

相关【板子】gcd、exgcd、乘法逆元、快速幂、快速乘、筛素数、快速求逆元、组合数

转载至：[http][][://www.cnblogs.com/flipped/p/5716603.html][http] 1.gcd in

清疚/ 2022年06月16日 08:28/ 0 赞/ 168 阅读

相关逆元详解求逆元的方法汇总

[基础知识][Link 1] [求乘法逆元的几种方法][Link 2] [逆元详解][Link 3] [Link 1]: http://blog.csdn.net/fe

秒速五厘米/ 2022年06月13日 05:45/ 0 赞/ 169 阅读

相关详解--乘法逆元

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

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

相关乘法逆元 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 赞/ 193 阅读

相关乘法逆元的求法（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 赞/ 730 阅读