AcWing89. a^b

题目

求 $a$ 的 $b$ 次方对 $p$ 取模的值。

输入格式

三个整数 $a,b,p,$ 在同一行用空格隔开。

输出格式

输出一个整数，表示 a^b mod p 的值。

数据范围

$0\le a,b\le 10^9$

$1\le p\le 10^9$

输入样例

3 2 7

输出样例

2

思路

快速幂。

任何一个整数都可以唯一表示为若干指数不重复的 2 的次幂的和。即是说如果 $b$ 在二进制表示下 $k$ 位，其中第 $i(0\le i\le k)$ 位的数字是 $c_i$，那么：
$$b=c_{k-1}{2}^{k-1}+c_{k-2}{2}^{k-2}+...+c_0{2}^0$$
于是
$$a^b=a^{c_{k-1}\times 2^{k-1}}\ast a^{c_{k-2}\times 2^{k-2}}\ast ...\ast a^{c_0\times 2^0}$$
因为 $k=\lceil lo{g}_2(b+1)\rceil$，所以上式乘积项的数量不多于 $k=\lceil lo{g}_2(b+1)\rceil$ 个。又因为：
$$a^{2^i}=(a^{2^{i-1}}{)}^2$$
所以可以通过 $k$ 次递归求出每个乘积项，当 $c_i=1$ 时，将该乘积项累积到答案中。KaTeX parse error: Expected 'EOF', got '&' at position 3: b &̲ 1 运算可以取出 $b$ 在二进制表示下的最低位，而 $b>>1$ 运算可以舍去最低位，在递推过程中将二者集合，就可以遍历 $b$ 在二进制表示下的所有数位 $c_i$。

整个算法的时间复杂度为 $O(lo{g}_{2}b)$。

代码

#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$ 取模以后，执行赋值操作时，该结果会被隐式转换成 int 存回 ans 中。