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 中。