数学/数论专题-学习笔记:乘法逆元


目录

1. 前言

本篇文章是作者学习乘法逆元的时候的一些学习笔记。

前置知识:同余式,一些简单的数论符号。

2. 详解

2.1 定义+作用

乘法逆元的定义如下:对于任意 /(a /in N_+/),若存在 /(a /in N_+/) 使得 /(ax /equiv 1 /pmod p/),则称 /(a/) 是 /(x/) 在模 /(p/) 意义下的数论倒数或者是乘法逆元,将 /(a/) 记作 /(x^{-1}/)。

实际上你会发现这玩意跟实数域上的倒数定义差不多,都是相乘为 1qwq

但是需要注意的是,并不是所有 /(x/) 在模 /(p/) 意义下都有逆元,如果 /(p /mid x/),那么 /(x/) 在模 /(p/) 意义下是没有逆元的,因为一定有 /(ax /equiv 0 /pmod p/)。

下面若无特殊说明,均认为任意数 /(x/) 在模 /(p/) 意义下有乘法逆元。

乘法逆元的一个很重要的作用就是做有理数域内的取模问题。

如果我们要求 /(/dfrac{a}{b} /bmod p/),那么根据 /(/dfrac{1}{b}=b^{-1}/),我们可以将式子变为 /(a /times b^{-1} /bmod p/),这样就可以通过求出 /(b^{-1}/) 来解决有理数取模问题。

乘法逆元的求法有三种:exgcd 求法,快速幂求法,线性递推式。

2.2 exgcd 求法

这个求法的前置知识:扩展欧几里得算法。

如果不知道可以看百度百科或者我写的博客

对于同余式 /(ax /equiv 1 /pmod p/),我们可以将该式转变为 /(ax+bp=1,b /in Z/)。

这样就可以通过 exgcd 求出该不定方程的特解,然后就可以求出乘法逆元了。

该方法的使用范围:/(/gcd(x,p)=1/)。

Code:

void exgcd(int a, int b, LL &x, LL &y)
{
    if (b == 0) {x = 1; y = 0; return ;}
    exgcd(b, a % b, x, y);
    LL p = x; x = y; y = p - ((LL)a / b) * y;
}

2.3 快速幂求法

这个求法的前置知识:费马小定理。

描述如下:如果 /(p /in Prime/),那么 /(a^{p-1} /equiv 1 /pmod p/)。

那么因此我们就可以考虑求逆元的时候对式子做个变形:

/[a /times a^{-1} /times a^{p-1} /equiv 1 /pmod p
/]

/[a /times a^{p-2} /equiv 1 /pmod p
/]

因此 /(a/) 的逆元是 /(a^{p-2}/)。

事实上这玩意你还可以用欧拉定理/扩展欧拉定理来推广,但是复杂度会升至根号级别,不如用第一种方法。

快速幂求法的使用范围:/(p /in Prime/)。

该方法对于确定模数为质数(如 /(998244353/))的题目比较方便。

Code:

LL ksm(LL fir, LL sec, LL p)
{
    LL ans = 1 % p;
    for (; sec; sec >>= 1, fir = fir * fir % p)
        if (sec & 1) ans = ans * fir % p;
    return ans;
}

2.4 线性递推式

前置知识:无。

这个算法可以 /(O(n)/) 求出 /([1.n]/) 内的所有数的乘法逆元。

首先显然的,/(1^{-1}=1/)。

接下来假设我们已经处理好了所有 /([1,n-1](n>1)/) 范围内的数的乘法逆元,要求 /(n^{-1}/)。

令 /(k=/left/lfloor/dfrac{p}{n}/right/rfloor,j=p /bmod n/),那么 /(p=kn+j/)。

那么有 /(kn+j /equiv 0 /pmod p/)。

两边同时乘上 /(n^{-1} /times j^{-1}/),有 /(kj^{-1}+n^{-1} /equiv 0 /pmod p/)。

移项,/(n^{-1} /equiv -kj^{-1} /equiv -/left/lfloor/dfrac{p}{n}/right/rfloor /times (p /bmod n)^{-1}/)。

由于 /(p /bmod n<n/),那么我们可以知道要求 /(n^{-1}/) 只需要知道所有 /([1,n-1]/) 内数的逆元。

因此原假设成立。

于是我们可以 /(O(n)/) 求出 /([1,n]/) 内的数的逆元。

该算法的使用范围:任意。

注意如果 /(p /mid i/) 时 /(i^{-1}/) 无意义,因此特别注意这种情况。

P3811 【模板】乘法逆元

Code:

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

3. 总结

  • 乘法逆元:对于任意 /(a /in N_+/),若存在 /(a /in N_+/) 使得 /(ax /equiv 1 /pmod p/),则称 /(a/) 是 /(x/) 在模 /(p/) 意义下的数论倒数或者是乘法逆元,将 /(a/) 记作 /(x^{-1}/)。
  • 三种求法:exgcd 求法,快速幂求法,线性递推式。

原创文章,作者:1402239773,如若转载,请注明出处:https://blog.ytso.com/245391.html

(0)
上一篇 2022年4月18日
下一篇 2022年4月18日

相关推荐

发表回复

登录后才能评论