快速幂
快速幂,二进制取幂(Binary Exponentiation,也称平方法),是一个在
算法描述¶
计算
首先我们将
因为
于是我们只需要知道一个快速的方法来计算上述 3 的
因此为了计算
将上述过程说得形式化一些,如果把
其中
根据上式我们发现,原问题被我们转化成了形式相同的子问题的乘积,并且我们可以在常数时间内从
这个算法的复杂度是
代码实现¶
首先我们可以直接按照上述递归方法实现:
1 2 3 4 5 6 7 8 | long long binpow(long long a, long long b) {
if (b == 0) return 1;
long long res = binpow(a, b / 2);
if (b % 2)
return res * res * a;
else
return res * res;
}
|
第二种实现方法是非递归式的。它在循环的过程中将二进制位为 1 时对应的幂累乘到答案中。尽管两者的理论复杂度是相同的,但第二种在实践过程中的速度是比第一种更快的,因为递归会花费一定的开销。
1 2 3 4 5 6 7 8 9 | long long binpow(long long a, long long b) {
long long res = 1;
while (b > 0) {
if (b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
|
模板:Luogu P1226
应用¶
模意义下取幂¶
问题描述
计算
这是一个非常常见的应用,例如它可以用于计算模意义下的乘法逆元。
既然我们知道取模的运算不会干涉乘法运算,因此我们只需要在计算的过程中取模即可。
1 2 3 4 5 6 7 8 9 10 | long long binpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1) res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
|
注意:根据费马小定理,如果
计算斐波那契数¶
问题描述
计算斐波那契数列第
根据斐波那契数列的递推式
多次置换¶
问题描述
给你一个长度为
简单地把这个置换取
注意:给这个置换建图,然后在每一个环上分别做
加速几何中对点集的操作¶
三维空间中,
个点 n ,要求将 p_i 个操作都应用于这些点。包含 3 种操作: m
- 沿某个向量移动点的位置(Shift)。
- 按比例缩放这个点的坐标(Scale)。
- 绕某个坐标轴旋转(Rotate)。
还有一个特殊的操作,就是将一个操作序列重复
次(Loop),这个序列中也可能有 Loop 操作(Loop 操作可以嵌套)。现在要求你在低于 k 的时间内将这些变换应用到这个 O(n \cdot \textit{length}) 个点,其中 n 表示把所有的 Loop 操作展开后的操作序列的长度。 \textit{length}
让我们来观察一下这三种操作对坐标的影响:
- Shift 操作:将每一维的坐标分别加上一个常量;
- Scale 操作:把每一维坐标分别乘上一个常量;
- Rotate 操作:这个有点复杂,我们不打算深入探究,不过我们仍然可以使用一个线性组合来表示新的坐标。
可以看到,每一个变换可以被表示为对坐标的线性运算,因此,一个变换可以用一个
使用这个矩阵就可以将一个坐标(向量)进行变换,得到新的坐标(向量):
你可能会问,为什么一个三维坐标会多一个 1 出来?原因在于,如果没有这个多出来的 1,我们没法使用矩阵的线性变换来描述 Shift 操作。
接下来举一些简单的例子来说明我们的思路:
-
Shift 操作:让
x 5 y 7 z 9 \begin{bmatrix} 1 & 0 & 0 & 5 \\ 0 & 1 & 0 & 7 \\ 0 & 0 & 1 & 9 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} -
Scale 操作:把
x y,z \begin{bmatrix} 10 & 0 & 0 & 0 \\ 0 & 5 & 0 & 0 \\ 0 & 0 & 5 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} -
Rotate 操作:绕
x \theta \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & \cos \theta & \sin \theta & 0 \\ 0 & -\sin \theta & \cos \theta & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}
现在,每一种操作都被表示为了一个矩阵,变换序列可以用矩阵的乘积来表示,而一个 Loop 操作相当于取一个矩阵的 k 次幂。这样可以用
定长路径计数¶
问题描述
给一个有向图(边权为 1),求任意两点
我们把该图的邻接矩阵 M 取 k 次幂,那么
模意义下大整数乘法¶
计算
。 a\times b\bmod m,\,\,a,b\le m\le 10^{18}
与二进制取幂的思想一样,这次我们将其中的一个乘数表示为若干个 2 的整数次幂的和的形式。因为在对一个数做乘 2 并取模的运算的时侯,我们可以转化为加减操作防止溢出。这样仍可以在
注意:你也可以利用双精度浮点数在常数时间内计算大整数乘法。因为
高精度快速幂¶
前置技能
请先学习 高精度
例题【NOIP2003 普及组改编·麦森数】(原题在此)
题目大意:从文件中输入 P(1000<P<3100000),计算
代码实现如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #include <bits/stdc++.h>
using namespace std;
int a[505], b[505], t[505], i, j;
int mult(int x[], int y[]) // 高精度乘法
{
memset(t, 0, sizeof(t));
for (i = 1; i <= x[0]; i++) {
for (j = 1; j <= y[0]; j++) {
if (i + j - 1 > 100) continue;
t[i + j - 1] += x[i] * y[j];
t[i + j] += t[i + j - 1] / 10;
t[i + j - 1] %= 10;
t[0] = i + j;
}
}
memcpy(b, t, sizeof(b));
}
void ksm(int p) // 快速幂
{
if (p == 1) {
memcpy(b, a, sizeof(b));
return;
}
ksm(p / 2);
mult(b, b);
if (p % 2 == 1) mult(b, a);
}
int main() {
int p;
scanf("%d", &p);
a[0] = 1;
a[1] = 2;
b[0] = 1;
b[1] = 1;
ksm(p);
for (i = 100; i >= 1; i--) {
if (i == 1) {
printf("%d\n", b[i] - 1);
} else
printf("%d", b[i]);
}
}
|
习题¶
- UVa 1230 - MODEX
- UVa 374 - Big Mod
- UVa 11029 - Leading and Trailing
- Codeforces - Parking Lot
- SPOJ - The last digit
- SPOJ - Locker
- LA - 3722 Jewel-eating Monsters
-
本页面部分内容译自博文 Бинарное возведение в степень 与其英文翻译版 Binary Exponentiation。其中俄文版版权协议为 Public Domain + Leave a Link;英文版版权协议为 CC-BY-SA 4.0。
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用