【数论】快速幂
一、快速幂的概念
快速幂，就是求某个数 a 的 k 次幂的一种快速方法。直接计算的时间复杂度为 O(n)，而使用快速幂的时间复杂度仅为 O(\log k)。
二、基本思路
我们来看一个简单的例子：求 a^k \bmod p。
思路一：暴力
直接循环求出 a^k，时间复杂度为 O(k)。当 k 较大时，容易超时。因此，我们可以采用快速幂算法。
思路二：快速幂
快速幂的基本思想是反复平方。
首先，我们预处理出：
这 \log k 个数。细心的读者可能已经发现，这些数恰好对应 k 的二进制展开中每一位的权值。于是，将 k 用二进制表示，就可以将 a^k 表示为若干上述数的乘积。
示例：
求 4^5。将 5 化为二进制 (101)_2，则：
因为二进制可以表示所有整数，所以我们只需通过 b & 1 判断当前二进制位是否为 1，若是，则乘上对应的底数幂；否则不乘。
但要注意，如何保证每次处理的位权正确呢？
方法是：每次循环都将底数平方，即从 a^{2^0} 变为 a^{2^1}，再变为 a^{2^2}，以此类推。这样，无论当前位是否为 1，底数都不断平方，从而与二进制位权对齐。
示例代码
typedef long long LL;
LL qmi(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = (LL)res * a % p;
b >>= 1;
a = (LL)a * a % p;
}
return res;
}
三、快速幂求逆元
1. 逆元的定义
若整数 b 与 m 互质，且对于任意整数 a，若 b \mid a，存在整数 x 使得：
则称 x 为 b 的模 m 乘法逆元，记为 b^{-1} \pmod{m}。
b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时，b^{m-2} 即为 b 的乘法逆元。
2. 逆元的求法
由逆元定义：
两边同时乘以 b：
因为 b 与 m 互质，且 a 可约，得到最简式：
由费马小定理：当 m 为质数 p 时，
即：
与 b \cdot x \equiv 1 \pmod{p} 对比，可得：
因此，b 的逆元即为 b^{p-2}，可用快速幂求解。
示例代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
LL qmi(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = (LL)res * a % p;
b >>= 1;
a = (LL)a * a % p;
}
return res;
}
int main() {
int n;
scanf("%d", &n);
while (n--) {
int a, p;
cin >> a >> p;
int res = qmi(a, p - 2, p);
if (a % p != 0) printf("%d\n", res);
else printf("impossible\n");
}
return 0;
}
四、例题讲解
例题：AcWing 1289. 序列的第 k 个数
BSNY 在学习等差数列和等比数列，已知前三项时，就可以判断是等差还是等比数列。
现在给你一个整数序列的前三项，这个序列要么是等差，要么是等比，请你求出第 k 项的值。如果结果太大，对其取模 200907。
输入格式
第一行一个整数 T，表示有 T 组测试数据。
每组测试数据输入前三项 a, b, c，然后输入 k。
输出格式
对于每组数据，输出第 k 项取模 200907 的值。
数据范围
- 1 \leq T \leq 100
- 1 \leq a \leq b \leq c \leq 10^9
- 1 \leq k \leq 10^9
输入样例
2
1 2 3 5
1 2 4 5
输出样例
5
16
解题思路
首先考虑：是否存在前三项既是等差又是等比的情况（除 a = b = c 外）？
实际上，除了常数数列，不存在其他情况。证明如下：
设首项为 x，若为等比数列，则第二项为 xd，第三项为 xd^2；
若为等差数列，则第二项为 x + p，第三项为 x + 2p。
若同时满足，则有：
显然，只有常数数列（包括全 0）满足，其他情况无解。
因此，我们只需判断是等差还是等比：
-
若为等差数列，公差 d = b - a，第 k 项为：
a + d \cdot (k - 1) -
若为等比数列，公比 q = \frac{b}{a}，第 k 项为：
a \cdot q^{k-1} = a \cdot \left(\frac{b}{a}\right)^{k-1}其中 q^{k-1} 可用快速幂计算。
参考代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 200907;
int qmi(int a, int k) {
int res = 1;
while (k) {
if (k & 1) res = (LL)res * a % N;
a = (LL)a * a % N;
k >>= 1;
}
return res;
}
int main() {
int n;
cin >> n;
while (n--) {
int a, b, c, k;
cin >> a >> b >> c >> k;
if (a + c == b * 2) { // 等价于 c - b == b - a
cout << (a + (b - a) * (LL)(k - 1)) % N << endl;
} else {
cout << (LL)a * qmi(b / a, k - 1) % N << endl;
}
}
return 0;
}