快速幂

快速幂

问题描述

求解$a^b%c$
其中$1\leq a,b,c\leq 10^9$

算法描述

首先需要知道模运算的乘法运算规则 : (a * b) % p = (a % p * b % p) % p
根据上面的规则,可以想到一种最朴素的快速幂算法,即将a依次累乘,同时不停对中间值进行取模运算,这不失为一种可行方案,但其复杂度为O(n),即使采取分治算法其时间复杂度也不会有明显下降,而快速幂算法的时间复杂度为O(log(n)),可以有效降低其运算时间。

学过计算机组成原理后我们知道整数在计算机中为二进制存储,由此我们可以将原式表示如下
$$a^{(2^{b_1}+2^{b_2}+…+2^{b_n})}$$
其中$0\leq b_1,b_2,\ldots,b_n\leq 1,b_n$代表b的二进制位中第n位的值,这样便可根据b的二进制位的权重对$b_1,b_2,\ldots,b_n$依次进行判断,若为真则乘以相应权重,这样只需将b的所有二进制位进行判断即可。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

ll qmod(ll a, ll b, ll c) {
ll ans = 1;
while (b) { // 依次判断二进制位
if (b & 1) ans = (ans * a) % c;
a = (a * a) % c; // 同步更新对应位置权重
b >>= 1;
}
return ans;
}

int main() {
ll a, b, c;
cin >> a >> b >> c;
cout << qmod(a, b, c) << endl;
return 0;
}
0%