AcWing89. a^b
题目
求 a a a 的 b b b 次方对 p p p 取模的值。
输入格式
三个整数 a , b , p , a,b,p, a,b,p, 在同一行用空格隔开。
输出格式
输出一个整数，表示 a^b mod p 的值。
数据范围
0 ≤ a , b ≤ 1 0 9 0≤a,b≤10^9 0≤a,b≤109
1 ≤ p ≤ 1 0 9 1≤p≤10^9 1≤p≤109
输入样例
3 2 7
输出样例
2
思路
快速幂。
任何一个整数都可以唯一表示为若干指数不重复的 2 的次幂的和。即是说如果
b
b
b 在二进制表示下
k
k
k 位，其中第
i
(
0
≤
i
≤
k
)
i(0 \le i \le k)
i(0≤i≤k) 位的数字是
c
i
c_i
ci，那么：
b
=
c
k
−
1
2
k
−
1
+
c
k
−
2
2
k
−
2
+
.
.
.
+
c
0
2
0
b = c_{k-1}2^{k-1} + c_{k-2}2^{k-2} + ... + c_0 2^0
b=ck−12k−1+ck−22k−2+...+c020
于是
a
b
=
a
c
k
−
1
×
2
k
−
1
∗
a
c
k
−
2
×
2
k
−
2
∗
.
.
.
∗
a
c
0
×
2
0
a ^b = a^{c_{k-1}\times2^{k-1}} * a^{c_{k-2} \times 2^{k-2}} * ... * a^{c_0 \times 2^0}
ab=ack−1×2k−1∗ack−2×2k−2∗...∗ac0×20
因为
k
=
⌈
l
o
g
2
(
b
+
1
)
⌉
k = \lceil log_2(b+1) \rceil
k=⌈log2(b+1)⌉，所以上式乘积项的数量不多于
k
=
⌈
l
o
g
2
(
b
+
1
)
⌉
k = \lceil log_2(b+1) \rceil
k=⌈log2(b+1)⌉ 个。又因为：
a
2
i
=
(
a
2
i
−
1
)
2
a^{2^i} = (a^{2^{i-1}})^2
a2i=(a2i−1)2
所以可以通过
k
k
k 次递归求出每个乘积项，当
c
i
=
1
c_i = 1
ci=1 时，将该乘积项累积到答案中。KaTeX parse error: Expected 'EOF', got '&' at position 3: b &̲ 1 运算可以取出
b
b
b 在二进制表示下的最低位，而
b
>
>
1
b >> 1
b>>1 运算可以舍去最低位，在递推过程中将二者集合，就可以遍历
b
b
b 在二进制表示下的所有数位
c
i
c_i
ci。
整个算法的时间复杂度为 O ( l o g 2 b ) O(log_2b) O(log2b)。
代码
#include <cstdio>
using namespace std;
int main() {
int a, b, p;
scanf("%d%d%d", &a, &b, &p);
int ans = 1 % p;
while (b) {
if (b & 1) ans = (long long)ans * a % p;
b >>= 1;
a = (long long)a * a % p;
}
printf("%d\n", ans);
return 0;
}
注意
在 C++ 语言中，两个数值执行算术运算时，以参与运算的最高数值类型为基准，与保存结果的变量类型无关。换言之，虽然两个 32 位整数的乘积可能超过 int 类型的表示范围，但是 CPU 只会用 1 个 32 位寄存器保存结果，造成越界现象。因此，必须把其中一个数强制转换成 64 位整数类型 long long 参与运算，从而得到正确的结果。最终对 p p p 取模以后，执行赋值操作时，该结果会被隐式转换成 int 存回 ans 中。