专栏文章

题解：P1226 【模板】快速幂

llangmouren
P1226题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miq1mxi8
此快照首次捕获于
2025/12/03 21:29
3 个月前
此快照最后确认于
2025/12/03 21:29
3 个月前
查看原文

快速幂 算法介绍

为什么要使用快速幂

如果按照正常方式求幂，则时间复杂度为 O(b)O(b)，速度在某些题是不够的（例如本题就只能拿到 6060 分）。
所以前人们想到了一种方法，能够在 O(log⁡2b)O(\log_2 b) 的时间内计算出结果。

快速幂举例

注：本章节仅举例，为什么要这么操作请见下文“算法正确性证明”。
首先约定一个初始值为 11 的 ansans 为答案。
例如，我们要计算 a11a^{11}，我们先把 1111 拆成二进制的 10111011。
10111011 的最后一位是 11，把 ansans 赋值为 ans×aans \times a，aa 赋值为 a×aa \times a，随后右移 10111011，使其变为 101101。
101101 的最后一位是 11，把 ansans 赋值为 ans×aans \times a，aa 赋值为 a×aa \times a，随后右移 101101，使其变为 1010。
1010 的最后一位是 00，把 aa 赋值为 a×aa \times a，随后右移 1010，使其变为 11。
11 的最后一位是 11，把 ansans 赋值为 ans×aans \times a，aa 赋值为 a×aa \times a，随后右移 11，使其变为 00。
00 运行下去没有任何意义了，结束。
此时我们就得到了正确的结果。

正确性证明

算法正确性证明

快速幂使用二进制来加快计算。
例如，我们要计算 a11a^{11}，因为 1111 的二进制是 10111011，我们可以转换出以下内容：
a11=a1011(2)=a23×1+22×0+21×1+20×1=a23×1+21×1+20×1=a23×a21×a20\begin{aligned} a^{11} &= a^{1011(2)} \\ &= a^{2^3 \times 1 + 2^2 \times 0 +2^1 \times 1 +2^0 \times 1}\\ &= a^{2^3 \times 1+2^1 \times 1 +2^0 \times 1}\\ &= a^{2^3} \times a^{2^1} \times a^{2^0} \end{aligned}
不需要有惊人的注意力就能发现，它的结果只和二进制中的非零项有关，所以在计算时我们只需要计算当前二进制位为 11 的位。
我们还可以通过指数的运算性质知道：
a2b×a2b=a2×2b=a2b+1a^{2^b} \times a^{2^b} = a^{2 \times 2^b} = a^{2^{b+1}}
高次幂可以通过低次幂求出，那么答案一定也可以从低次幂求出。
同时，由模运算的性质可以知道，在快速幂的运算过程中取模不会影响答案的正确性。

时间复杂度证明

对于任何一个数 bb，它有 ⌊log⁡2b⌋+1\lfloor \log_2 b \rfloor + 1 个二进制位，所以时间复杂度为 O(log⁡2b)O(\log_2 b)。

代码实现

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

long long a,b,p,ans=1; 

long long poww(long long a,long long b,long long p){
	while(b>0){//如果b还不是0
		if(b&1) ans=ans*a%p;//如果最低位是1 就把ans*a
		a=a*a%p;//不论最低位是不是1，a都需要自乘以升幂
		b>>=1;//b右移一位
	}
	return ans;
}

int main(){
	scanf("%d%d%d",&a,&b,&p);
	printf("%d^%d mod %d=%d",a,b,p,poww(a,b,p));
	return 0;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...