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)

。

模板题参考代码：

CPP

#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})

。

模板题参考代码：

CPP

#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

也存不下，故需要写快读，边读边取模。

模板题参考代码：

CPP

#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}

模板题参考代码：

CPP

#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

）

CPP

#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

感谢大家的阅读，再会！(^_−)☆

[数学]乘法逆元

文章操作

0.前言

1.定义

2.求逆元的方法

1.拓展欧几里得求逆元

2.欧拉定理求逆元

3.费马小定理求逆元

4.线性求逆

5.离线逆元

3.后记

相关推荐

评论

[数学]乘法逆元