Nickel_Angel's nest

Nickel_Angel's nest

The key to magic is inside of us.

[数学]乘法逆元

posted on 2019-07-19 11:12:01 | under 学习笔记 |

0.前言

在 $OI$ 中,大多数情况下,善良的出题人为了避免高精度等大整数计算,常常会要求输出答案对一个数(大多是质数)取模的情况,但这衍生了一个问题:若题目中计算需用到除法而我们知道,如果 $a \equiv b \pmod{c}$ 在大部分情况下 $\lfloor \frac {a} {d} \rfloor \not\equiv \lfloor \frac {b} {d} \rfloor \pmod{c}$(注意一般题目会默认对一个数取模是数论(整数)意义上的取模,故这里除法为整数除法),这和等式的性质是不同的,要解决这个问题,就需要用到一个概念:乘法逆元。

本文主要介绍乘法逆元的定义以及其求法QwQ

1.定义

如果您到百度上搜索逆元,您会看到如下定义:(这里逆元素是逆元的全称)

逆元素是指一个可以取消另一给定元素运算的元素

---百度百科

这个定义似乎不太那么直观……

我们来举个例子吧,先再实数范围举例,由小学知识可知,如果一个代数式 $F$ 乘一个数 $a$ 后,再乘它的倒数 $\frac {1} {a}$,相当于没有乘 $a$(这里不考虑 $0$ 的情况),换句话说,我们乘 $\frac {1} {a}$ 后,取消了代数式 $F$ 乘 $a$ 后值增大的影响。

不难发现这符合逆元的定义,故我们可以说一个数和其倒数互为乘法逆元。除此之外,我们还能发现一个数和其相反数互为加法逆元等等……

接下来回到代数式的例子,考虑为什么 $a$ 的倒数 $\frac 1 a$ 能消去乘 $a$ 的影响。显然,是由于乘法结合律的存在,使得我们在运算 $F \times a \times \frac 1 a$ 时可以先运算 $a \times \frac 1 a$ 的值,再运算它和 $F$ 的乘积,而 $a \times \frac 1 a = 1$,任何数与 $1$ 的乘积均为其本身,从而使乘 $a$ 对 $F$ 值增大的影响取消。

上文在实数范围内讨论了乘法逆元,现在我们来看本文主要讨论的内容,数论模意义下的乘法逆元。

由上文的分析来看,我们可以借助“任何数与$1$的乘积均为其本身”的性质定义模意义下的乘法逆元。

故其定义为:如果说 $a$ 在模 $p$ 意义下的乘法逆元是 $x$,那么 $ax \equiv 1 \pmod{p}$

我们通常将 $a$ 的逆元记作 $a^{-1}$。

如同 $0$ 没有倒数一样,$0$ 也没有乘法逆元。

不难发现,$a$ 在模 $p$ 意义下的乘法逆元均为 $[1,p - 1]$ 中的整数。

2.求逆元的方法

单个数求逆元模板

1.拓展欧几里得求逆元

不难发现 $ax \equiv 1 \pmod {p}$ 可以写成 $ax + py = 1$ 的形式:

将同余号换为等号得:

$$ax\,mod\,p = 1\,mod\,p$$

移项得:

$$(ax - 1)\,mod\,p = 0$$

由上式可知 $ax - 1$ 为 $p$ 的整数倍,不妨设其为 $p$ 的 $k(k \in Z)$ 倍:

$$ax - 1 = kp$$

继续移项得:

$$ax - kp = 1$$

令 $y = -k$,就写成了上文的形式:$ax + py = 1$

我们可以通过不断迭代的方式来求解单个数的逆元,这里涉及到了解线性同余方程的知识,可以看我的另一篇文章

我们发现这个方程有解的条件是 $gcd(a,p) \mid 1$,即 $gcd(a,p) = 1$,$a,p$ 互质,所以得出结论:$a$ 在模$p$ 意义下的乘法逆元存在当且仅当 $a,p$ 互质,这也在一定程度上解释了大多数题目模数为什么为质数的原因:(设模数为 $p$)可以保证在 $[1,p - 1]$ 中的所有整数都有模 $p$ 意义下的逆元。

而由于 $gcd(a,p) = 1$,故我们可以直接运用拓展欧几里得算法解 $ax + py = gcd(a,p)$ 这个方程。

时间复杂度为 $O(\log p)$。

模板题参考代码:

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

long long a, b;

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

int main()
{
    scanf("%lld%lld", &a, &b);
    long long x = 0, y = 0;
    exgcd(a, b, x, y);
    printf("%lld", (x % b + b) % b);//这里防止出现负数
    return 0;
}

2.欧拉定理求逆元

观察式子 $ax \equiv 1 \pmod{p}$,我们发现它和欧拉定理 $a^{\varphi(p)} \equiv 1 \pmod{p}$ 很像……

而欧拉定理又是 $a,p$ 互质时成立,这和逆元存在的条件相同……

故将两个式子合在一起,得:

$$ax \equiv a^{\varphi(p)} \pmod{p}$$

两遍同除$a$得:

$$x \equiv a^{\varphi(p) - 1} \pmod{p}$$

故 $x = a^{\varphi(p) - 1}\,mod\,p$

我们可以在 $O(\sqrt{p})$ 的时间内求出单个数的欧拉函数。

引理:设 $n = p_1^{k_1} \times p_2^{k_2} \times \cdots \times p_m^{k_m} = \prod_{i = 1}^{m} p_i^{k_i}$ 为正整数 $n$ 的质数幂乘积表示式,则:

$\varphi(n) = n \times (1 - \frac {1} {p_1}) \times (1 - \frac {1} {p_2}) \times \cdots \times (1 - \frac {1} {p_m}) = n \times \prod_{i = 1}^{m} (1 - \frac {1} {p_i})$

证明:

由于各质数幂之间是互质的,根据欧拉函数的性质可得:

$$\begin{aligned} \varphi(n) & = \prod_{i = 1}^{m} \varphi(p_i^{k_i}) \\ & = \prod_{i = 1}^{m} p_i^{k_i} \times \prod_{i = 1}^{m} (1 - \frac {1} {p_i}) \\ & = n \times \prod_{i = 1}^{m} (1 - \frac {1} {p_i}) \end{aligned}$$

进而得证。

在求一个数的欧拉函数时,不妨将上式后面的分数部分通分化作 $\varphi(n) = n \times \prod_{i = 1}^{m} (\frac {p_i - 1} {p_i})$,我们可以在 $O(\sqrt{n})$ 的时间内枚举 $n$ 的每个质因子,初始化 $ans$ 为 $n$,每枚举到一个质因子 $p_i$ 就让 $ans \times \frac {p_i - 1} {p_i}$,发现每个质因子只对答案贡献一次,故在统计完该质因子的答案后,这个质因子就无用了,为了方便最后判断我们是否将$n$的所有质因子全都枚举到,我们可以通过不断除该质因子来消去它,防止其再被计入答案。

求出欧拉函数后,可以使用快速幂求出答案。

故这样做的时间复杂度为 $O(\log \varphi(p) + \sqrt{p})$。

模板题参考代码:

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

long long n, p;

long long phi(long long x)//求x的欧拉函数
{
    long long res = x, tmp = x;//初始化答案为x
    for (int i = 2; i * i <= tmp; ++i)
    {
        if (x % i == 0)
        {
            res = (res / i) % p * ((i - 1) % p) % p;//找到x的一个质因子,计算其对答案的贡献
            while (x % i == 0) x /= i;//统计完答案后,除去该质因子
        }
    }
    if (x > 1) res = (res / x) % p * ((x - 1) % p) % p;//防止漏筛质因子
    return res;
}

long long power(long long a, long long b)//快速幂
{
    long long res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

int main()
{
    scanf("%lld%lld", &n, &p);
    long long tmp = phi(p) - 1;
    printf("%lld", power(n, tmp));
    return 0;
}

3.费马小定理求逆元

注意,这种求逆元的方法仅使用在 $p$ 为质数的时候

费马小定理:若 $p$ 为质数,且整数 $a$ 满足 $p \nmid a$,则有 $a^{p-1} \equiv 1 \pmod{p}$

对于定理中的式子,我们可以将两边同除$a$,得:

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

而 $a^{-1}$ 就是 $a$ 在模 $p$ 意义下的乘法逆元。

故我们只需计算 $a^{p - 2}\,mod\,p$ 即可,而这个过程可用快速幂解决。

时间复杂度为 $O(\log p)$

我们不妨看看本文开篇提出的问题,如何对一个分数取模?

一般的讲,我们是这么定义分数取模的:

我们设 $\frac {a} {b}\,mod\,p$ 的值为一个整数 $x$,其满足 $bx \equiv a \pmod{p}$且 $x \in [0,p - 1]$。

我们只需求出 $x$ 的值即可。而上式两边同乘 $b$ 在模 $p$ 意义下的乘法逆元 $b^{-1}$ 后可得:$x \equiv ab^{-1} \pmod{p}$

而 $x$ 的范围在模 $p$ 剩余系内,故可直接写作 $x = ab^{-1}\,mod\,p$

有理数取余模板题

在本题中,$p = 19260817$,是个质数,故可以直接使用费马小定理求逆元。

但注意:

$1.$ 当 $b \equiv 0 \pmod{p}$ 时,费马小定理不成立,故无解。

$2.$ 本题 $a,b$ 数据范围很大,$long\,long$ 也存不下,故需要写快读,边读边取模。

模板题参考代码:

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <iostream>

using namespace std;

const int p = 19260817;

template<typename T>
inline void input(T &x)
{
    x = 0;
    char ch = getchar();
    bool f = false;
    while (!isdigit(ch))
    {
        f |= (ch == '-');
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        x %= p;//边读边取模
        ch = getchar();
    }
    x = f ? -x : x;
}

inline int power(int a, int b)//快速幂
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = 1ll * res * a % p;
        a = 1ll * a * a % p;
        b >>= 1;
    }
    return res;
}

int main()
{
    int a, b;
    input(a), input(b);
    if (!b) 
        puts("Angry!");//b % p = 0 时无解
    else
        printf("%d", (int)(1ll * a * power(b, p - 2) % p));
    return 0;
}

4.线性求逆

线性求逆模板题

注意,这种求逆元的方法仅使用在 $p$ 为质数的时候

基于拓展欧几里得算法,我们虽然可以在 $O(n \log p)$ 时间内,求出 $[1,n]\,(1 \leq n < p)$ 中所有整数在模质数 $p$ 下的乘法逆元,但在面对更大的数据范围时,我们就需要更快的方法。

首先,我们不难发现,对于任何正整数 $c$ ,$1^{-1} \equiv 1 \pmod{c}$,即 $1$ 在模任意正整数意义下的逆元为其本身。

然后设 $p = ki + r\,(r < i,1 < i < p)$,将其转化为同余式会得到:

$$ki + r \equiv 0 \pmod{p}$$

两边同时乘 $i^{-1},r^{-1}$,得:

$$i^{-1}r^{-1}(ki + r) \equiv 0 \pmod{p}$$

将式子乘开:

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

移项得:

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

由 $p = ki + r\,(r < i,1 < i < p)$ 易知 $k = \lfloor \frac {p} {i} \rfloor , r = p\,mod\,i$,故有:

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

而 $p\,mod\,i < i$,故 $p\,mod\,i$ 的逆元我们之前已经递推出来了,故我们可以通过这个式子推出 $i$ 的逆元是谁。

综上,我们在已知 $1$ 的逆元为 $1$ 的情况下,可以推出 $[1,n]\,(1 \leq n < p)$ 中所有整数在模质数 $p$ 下的乘法逆元。

这个算法的时间复杂度为 $O(n)$。

注意 $- \lfloor \frac {p} {i} \rfloor$ 为负数,但在模 $p$ 意义下,其等价于 $p - \lfloor \frac {p} {i} \rfloor$,故在实际应用中真正的递推式为:

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

模板题参考代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 3e6 + 10; 
long long inv[maxn], n, p;

int main()
{
    scanf("%lld%lld", &n, &p);
    inv[0] = 0, inv[1] = 1;//初始化1的逆元为1
    printf("%lld\n", inv[1]);
    for (int i = 2; i <= n; ++i)
    {
        inv[i] = (p - p / i) * inv[p % i] % p;//上文中的式子
        printf("%lld\n", inv[i]);
    }
    return 0;
}

5.离线逆元

离线逆元模板题

在 2019 年十二省联考中某个 std 长达 800(900?) 多行的题中用到了这个新知识。

其实也不算全新的知识,似乎在以前这种方法只是被用来求阶乘逆元,最近才逐渐扩展到一般情况

这个算法用途是:对于给定的 $n$ 个整数 $a_1,a_2,\cdots,a_n$,求它们在模 $p$ 意义下的乘法逆元。

$O(max(a_i))$ 的递推显然不适用,时间空间双双爆炸。

基于拓展欧几里得算法或费马小定理的 $O(n \log p)$ 的朴素算法也会超时,我们需要一种接近线性的算法。

我们不妨设 $pre_i$ 为 $a_1,a_2, \cdots ,a_i$ 的前缀积(即 $pre_i = \prod_{j = 1}^{i} a_j$)

然后我们就用到了一个 $trick$:前缀积的逆元就是逆元的前缀积(即逆元是完全积性的)

我们不妨来证明一下逆元是完全积性的,即证明对于任意正整数 $a,b$,它们在模 $p$ 意义下的逆元满足:

$$a^{-1} \times b^{-1} \equiv (ab)^{-1} \pmod{p}$$

根据逆元的定义,$a,b$ 在模 $p$ 意义下的逆元满足:

$$a \times a^{-1} \equiv 1 \pmod{p} \quad b \times b^{-1} \equiv 1 \pmod{p}$$

将两个式子相乘得:

$$a \times b \times a^{-1} \times b^{-1} \equiv 1 \pmod{p}$$

不难发现上式中 $a^{-1} \times b^{-1}$ 符合 $(ab)^{-1}$ 的定义,于是 $a^{-1} \times b^{-1} \equiv (ab)^{-1} \pmod{p}$,从而得证。

故我们利用费马小定理求出的 $pre_n$ 的逆元,它其实是 $a_1^{-1},a_2^{-1},\cdots,a_n^{-1}$ 的前缀积(即 $pre_n^{-1} = \prod_{j = 1}^{n} a_j^{-1}$)

而 $a_i^{-1} = \prod_{j = 1}^{i - 1} a_j \times \prod_{j = 1}^{i} a_j^{-1} = pre_{i - 1} \times pre_i^{-1}$,故我们求出可以从$n$开始,在求出 $pre_n^{-1}$ 后,利用 $pre_i^{-1} = a_{i + 1} \times \prod_{j = 1}^{i + 1} a_j^{-1} = a_{i + 1} \times pre_{i + 1}^{-1}$递推出 $pre_i^{-1}$,再用前文的式子递推出 $a_i^{-1}$ 即可。

综上,递推式为:

$$pre_i^{-1} = a_{i+1} \times pre_{i + 1}^{-1}(1 \leq i < n)$$

$$a_j^{-1} = pre_{j - 1} \times pre_j^{-1}(1 \leq j \leq n)$$

(其中 $pre_n^{-1}$ 已求出,$pre_0 = 1$)

这种求逆元的方法的时间复杂度为 $O(n + \log p)$,已经接近线性。

模板题参考代码:(注意常数优化和防爆 $int$)

#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>

using namespace std;

template<typename T>
inline void input(T &x)//本题卡常数,需要用快读
{
    x = 0;
    register char ch = getchar();
    register bool f = false;
    while (!isdigit(ch))
    {
        f |= (ch == '-');
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    x = f ? -x : x;
}

const int maxn = 5e6 + 10;
int n, p, k, a[maxn], inv[maxn], pre[maxn], inv_pre[maxn];

inline int power(int a, int b, int p)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = 1ll * res * a % p;
        a = 1ll * a * a % p;
        b >>= 1;
    }
    return res;
}

int main()
{
    input(n), input(p), input(k);
    pre[0] = 1;//初始化
    for (register int i = 1; i <= n; ++i)
    {
        input(a[i]);
        pre[i] = 1ll * pre[i - 1] * a[i] % p;//计算前缀积
    }
    inv_pre[n] = power(pre[n], p - 2, p);//求出前缀积的逆元
    for (register int i = n; i > 0; --i)//递推求逆元
    {
        inv[i] = 1ll * pre[i - 1] * inv_pre[i] % p;
        inv_pre[i - 1] = 1ll * inv_pre[i] * a[i] % p;
    }
    int ans = 0;//计算题目中式子的值
    for (register int i = 1, t = k; i <= n; ++i)
    {
        ans = (1ll * inv[i] * t % p + ans) % p;
        t = 1ll * t * k % p;
    }
    printf("%d", ans);
    return 0;
}

3.后记

本文部分参考了《信息学奥赛之数学一本通》(东南大学出版社)中的内容。

$Upd\,2019-8-21:$

感谢 @Wallace 指出本文在分析“欧拉定理求逆元”时的时间复杂度上的错误。

感谢 @WYXkk 提供了当 $p$ 不是质数时,线性递推求模 $p$ 意义下的逆元的方法。

$Upd\,2019-8-23:$

感谢 @Liuier 指出本文推导“离线逆元”的式子时出现的错误。

$Upd\,2019-8-24:$

当 $p$ 不是质数时,线性递推求模 $p$ 意义下的逆元的方法被证明是错误的……决定撤下QAQ

补充了逆元的完全积性的证明QwQ

感谢大家的阅读,再会!(^_−)☆