简介

在模运算中，我们并不直接处理整数本身，而是处理它们除以 $m$ 后的余数， 这一过程称为“对 $m$ 取模”。例如，当 $m = 23$ 时，我们不直接使用 $x = 247$，而使用 $x \bmod 23 = 17$。通常，题目会给出一个很大的质数 $m$；最常见的两个模数是 $10^9 + 7$ 和 $998\,244\,353=119\cdot 2^{23}+1$。模运算可以避免数值超出内置数据类型 所能表示的范围，因为我们可以按照下列公式随时取余：

模幂

资料

二进制快速幂可以高效计算 $x ^ n \mod m$。其思想是把指数 $n$ 按二进制 拆分。例如，$5 ^ {10}=5 ^ {1010_2}=5 ^ 8 \cdot 5 ^ 2$。因此，只要我们 知道所有指数为二的幂时的 $x ^ y$（即 $x ^ 1$、$x ^ 2$、$x ^ 4$、 $\dots$、$x ^ {2^{\lfloor{\log_2n} \rfloor}}$），就能在 $\mathcal{O}(\log n)$ 时间内计算 $x ^ n$。

为了处理模数 $m$，注意取模与乘法相容。因此可以直接实现上述二进制快速幂， 并在每次乘法后将结果对 $m$ 取模。

题解——Exponentiation

Copy
MOD = 10**9 + 7

for _ in range(int(input())):
	first, second = [int(i) for i in input().split()]
	print(pow(first, second, MOD))

模逆元

模逆元对应于实数运算中的倒数：要在模意义下用 $a$ 除以 $b$，可以将 $a$ 乘以 $b$ 的模逆元。这里我们只考虑模数 $p$ 为质数的情况。

例如，$2$ 在模 $p=10^9+7$ 下的逆元为 $i=\frac{p+1}{2}=5\cdot 10^8+4$。这意味着对任意整数 $x$，都有

例如，$10i\equiv 5\pmod{10^9+7}$。

使用快速幂

费马小定理 （不要与费马大定理混淆）指出：对于所有不能被 $p$ 整除的整数 $a$， 都有 $a^{p - 1} \equiv 1 \pmod{p}$。于是 $a^{p-2} \cdot a \equiv 1 \pmod{p}$，因此 $a^{p - 2}$ 就是 $a$ 在模 $p$ 意义下的一个逆元。

Copy
MOD = 10**9 + 7

x = pow(2, MOD - 2, MOD)
print(x)  # 500000004
assert 2 * x % MOD == 1

使用欧几里得除法

我们还可以通过欧几里得除法求模逆元。给定质数模数 $m > a$，有：

其中 $k = \lfloor \frac{m}{a} \rfloor$，$r = m \mod a$。于是：

下面是上述公式的一份简短递归实现：

Copy
def inv(x: int) -> int:
	return x if x <= 1 else MOD - MOD // x * inv(MOD % x) % MOD

这种方法的优点是，可以在 $\mathcal{O}(MOD)$ 时间内预处理区间 $[1, MOD)$ 中所有数的模逆元。

Copy
inv[1] = 1  # assume we already defined this array
for i in range(2, MOD):
	inv[i] = MOD - MOD / i * inv[MOD % i] % MOD

由于计算模 $p$ 的逆元需要 $\mathcal{O}(\log p)$ 时间，在循环中频繁进行除法 会显著增加程序运行时间。如果同一个（或同一批）数的逆元会被多次使用，最好 提前将其预处理出来。

此外，必须始终确保不会除以 $0$。需要注意的是，一个非零数取模后也可能变成 $0$，因此除数不是常量时尤其要小心。

Copy
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

 Code Snippet: ModInt (Click to expand)

int main() {
	{
		int a = 1e8, b = 1e8, c = 1e8;

Copy
#include <bits/stdc++.h>
using namespace std;

// https://atcoder.github.io/ac-library/production/document_en/modint.html
// (included in atcoder grading)
#include <atcoder/modint>
using mint = atcoder::modint;

const int MOD = 1e9 + 7;

练习题