快速幂

什么是幂

幂是一个数自乘若干次的形式，乘方的结果叫做幂。比如 $n$ 的 $m$ 次幂意为 $m$ 个 $n$ 相乘，写作 $n^{m}$ ，其中 $n$ 称为底数， $m$ 称为指数。

幂运算的性质

这些性质都是针对任意实数 $a, b$ 以及自然数 $n, m$ 所得的结论。

同底数幂的乘法法则 $a^{n} \times a^{m} = a^{n + m}$

同底数幂的除法法则 $a^{n} / a^{m} = a^{n - m}$

幂的幂 $(a^{n})^{m} = a^{n \times m}$

积的幂 $(a \times b)^{n} = a^{n} \times b^{n}$

商的幂 $(a / b)^{n} = a^{n} / b^{n}$

线性求幂

容易想到，求 $a^{n}$ 只需要循环 $n$ 次，每次乘 $a$ 即可，时间复杂度是 $O (n)$ ，代码如下：

int sum=1;
for (int i=1; i<=n; i++) sum *= a;

那能否更快呢？

快速幂

来看例题：

例题——快速幂

题目描述

给定 $n$ 组 $a i, b i, p i$ ，对于每组数据，求出 $a_{i}^{b_{i}} m o d p_{i}$ 的值。

输入格式

第一行包含整数 $n$ 。

接下来 $n$ 行，每行包含三个整数 $a i, b i, p i$ 。

输出格式

对于每组数据，输出一个结果，表示 $a_{i}^{b_{i}} m o d p_{i}$ 的值。

每个结果占一行。

样例输入

2
3 2 5
4 3 9

样例输出

4
1

题目分析

首先我们需要知道幂运算的性质， $a^{m} \times a^{n} = a^{m + n}$ ，又因在位运算章节中，我们学习过数字转二进制，必然可以把数字 $k$ 转为 $2^{x_{0}} + 2^{x_{1}} + \dots + 2^{x_{i}}$ 的形式，综合起来可得：

a^{k} = a^{(2^{x_{0}} + 2^{x_{1}} + \dots + 2^{x_{i}})}

举个例子：

5^{20} = 5^{2^{2} + 2^{4}}

这样表示有什么好处呢，请看下面的式子：

\begin{aligned} 5^{2^{1}} & = 5^{2^{0}} \times 5^{2^{0}} \\ 5^{2^{2}} & = 5^{2^{1}} \times 5^{2^{1}} \\ \dots \\ 5^{2^{x_{i}}} & = 5^{2^{x_{i - 1}}} \times 5^{2^{x_{i - 1}}} \end{aligned}

易得：

a^{2^{k}} = a^{2^{k - 1}} \times a^{2^{k - 1}}

这意味着什么呢？如果我们把 $a^{k}$ 拆解成 $a^{(2^{x_{0}} + 2^{x_{1}} + \dots + 2^{x_{i}})}$ 的形式，那么我们就可以利用上面的公式，从 $a^{2^{0}}$ 开始，一路往上递推，直到 $a^{2^{x_{i}}}$ ，并在这个过程中把所有要的数字都乘起来求出结果。
而把 $k$ 拆成二进制的时间复杂度为 $O (\log k)$ ，所以只需要这个复杂度就可以求出 $a^{k}$ 。

示例代码

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

long long qmi(int a, int k, int p) {
	long long res = 1;
	while (k) {
		if (k&1) res = res*a % p;  // 如果二进制上这位有数字，那么结果乘起来
		k >>= 1;  // 去掉最低位
		a = (long long)a*a % p;  // 递推求出 a^(2^x) 的值
	}
	return res;
}

int main() {
	int a, k, p;
	cin >> a >> k >> p;
	cin >> a >> k >> p;
	cout << qmi(a, k, p) << '\n';
	return 0;
}

例题——快速幂求逆元

题目描述

给定 $n$ 组 $a_{i}, p_{i}$ ，其中 $p_{i}$ 是质数，求 $a_{i}$ 模 $p_{i}$ 的乘法逆元，若逆元不存在则输出 impossible。

注意：请返回在 $0 \sim p - 1$ 之间的逆元。

乘法逆元的定义

若整数 $b, m$ 互质，并且对于任意的整数 $a$ ，如果满足 $b | a$ ，则存在一个整数 $x$ ，使得 $\frac{a}{b} \equiv a \times x (m o d m)$ ，则称 $x$ 为 $b$ 的模 $m$ 乘法逆元，记为 $b - 1 (m o d m)$ 。

$b$ 存在乘法逆元的充要条件是 $b$ 与模数 $m$ 互质。当模数 $m$ 为质数时， $b^{m - 2}$ 即为 $b$ 的乘法逆元。

输入格式

第一行包含整数 $n$ 。

接下来 $n$ 行，每行包含一个数组 $a_{i}, p_{i}$ ，数据保证 $p_{i}$ 是质数。

输出格式

输出共 $n$ 行，每组数据输出一个结果，每个结果占一行。

若 $a_{i}$ 模 $p_{i}$ 的乘法逆元存在，则输出一个整数，表示逆元，否则输出 impossible。

样例输入

样例输出

1
2
impossible

题目分析

在模运算中，我们都知道，加法和乘法是比较简单的：

\begin{array}{r} (A + B) % m o d = ((A % m o d) + (B % m o d)) % m o d \\ (A \times B) % m o d = ((A % m o d) \times (B % m o d)) % m o d \end{array}

减法因为可能由负数，所以需要加上之后再取模：

(A - B) % m o d = ((A % m o d) - (B % m o d) + m o d) % m o d

而除法取模则比较特别，这里我们需要引入逆元的概念。

逆元的概念

首先我们要来了解 单位元 和逆元的定义。

单位元

单位元的定义

在一个集合中，对于某种运算，如果对于任何的集合元素 $a$ ，和元素 $e$ 运算后还是得到集合元素 $a$ 本身，则称 $e$ 为这个运算下的单位元。

例如，在加法运算中，对于任意的实数 $a$ ，都有 $a + 0 = 0 + a = a$ ，所以加法运算的单位元 $e = 0$ 。
根据上面的概念，你可以说出乘法运算的单位元是什么么？

没错，就是 $1$ ！

逆元

逆元的定义

在一个集合中，对于某种运算，如果任意两个元素的运算结果等于单位元，则称这两个元素互为逆元。

例如，在普通的加法运算中，任意实数 $a$ 的逆元为 $- a$ 。

同理，在普通的乘法运算中，任意实非零实数 $a$ 的逆元为 $a^{- 1}$ 。

模乘运算下的单位元

对于结果对 $n$ 取模的乘法，首先所有模 $n$ 和 $a$ 同余的数都可以表示成：

a (m o d n) \equiv k \times n + a (k \in Z)

假设单位元为 $e (m o d n)$ ，我们将 $a (m o d n)$ 和 $e (m o d n)$ 进行模乘操作，得到：

\begin{aligned} a (m o d n) \times e (m o d n) & \equiv (k_{1} n + a) (k_{2} n + e) \\ \equiv (k_{1} k_{2} n^{2} + k_{1} e n + k_{2} a n + a e) \\ \equiv (k_{1} k_{2} n + k_{1} e n + k_{2} a) n + a e \end{aligned}

根据单位元的定义，应该有：

a (m o d n) \times e (m o d n) \equiv a (m o d n)

将上面的式子带入，则有：

(k_{1} k_{2} n + k_{1} e n + k_{2} a) n + a e = k \times n + a

所以可得：

{\begin{cases} k_{1} k_{2} n + k_{1} e n + k_{2} a = k \\ e = 1 \end{cases}

所以，模乘的单位元就是 $1 (m o d n)$ 。

模乘的逆元

根据逆元的定义，若 $a, n$ 互质，当 $a x \equiv 1 (m o d n)$ 时， $x$ 为逆元，记作 $x = a^{- 1}$ 。

例如： $8 x \equiv 1 (m o d 5)$ ，解得 $x = 2, 7, 12 \dots$ ，一般只考虑比 $n$ 小的，所以逆元为 $2$ 。

模乘逆元的定义

换个角度说，若 $a, n$ 互质，并且 $b | a$ ，则存在一个整数 $x$ ，使得 $a / b \equiv a \times x (m o d n)$ ，则称 $x$ 为 $b$ 模 $n$ 意义下的乘法逆元，记作 $b^{- 1} (m o d n)$ ，化简可以写成 $b x \equiv 1 (m o d n)$ 。

模乘逆元的一些性质：

性质

模 $n$ 意义，逆元一般只考虑比 $n$ 小的，并且在这个范围内逆元是唯一的。
逆元存在的条件， $a, n$ 互质，那么 $a$ 在模 $n$ 意义下才有逆元。

这个逆元有什么用呢？在取模意义下，如果数字 $a$ 的逆元为 $x$ ，那么在除以 $a$ 相当于乘以 $x$ ，所以就把除法运算变成了乘法运算。

那么如何求出数字的模乘逆元呢？我们先来了解一下费马小定理：

费马小定理

若 $p$ 是一个质数，且整数 $a$ 不是 $p$ 的倍数，则 $a^{p - 1} \equiv 1 (m o d p)$ 。也就是说，如果整数 $a$ 不能被质数 $p$ 整除，那么 $a^{p - 1} / p$ 得到的余数是 $1$ 。

那么根据逆元的定义和费马小定理，我们可以进行如下推导：

假设 $b, n$ 互质， $x$ 为 $b$ 的模乘逆元，有：

b \times x \equiv 1 (m o d n)

根据费马小定理，有：

b^{n - 1} \equiv 1 (m o d n)

将左边式子提取一个 $b$ 出来，得：

b \times b^{n - 2} \equiv 1 (m o d n)

所以可得，逆元 $x = b^{n - 2}$ 。

总结：

费马定理求乘法逆元

若 $b, n$ 互质，且模数 $n$ 是质数时， $b^{n - 2}$ 即为 $b$ 的乘法逆元。

做法其实很简单，因为 $p_{i}$ 已经限制是质数了，只需要判断一下 $a_{i}, p_{i}$ 是否互质，是则求 $a_{p - 2}$ ，否则就是 impossible。

示例代码

int n;
cin >> n;
while (n--) {
	int a, p;
	cin >> a >> p;
	if (a%p == 0) cout << "impossible\n";
	else cout << qmi(a, p-2, p) << '\n';  // 快速幂代码和上面一致，不再演示
}