AcWing 89. a^b

题目链接：89. a^b - AcWing题库

如果 $b$ 在二进制表示下有 $ k $ 位，其中第 $i(0 \le i < k)$ 位的数字是 $c_i$ ，那么：

\[b = c_{k - 1} 2^{k - 1} + c_{k - 2} 2^{k - 2} + \cdots + c_{0} 2^{0}\]

于是：

\[{a^b} = a^{c_{k - 1} * 2^{k - 1}} * a^{c_{k - 1} * 2^{k - 1}} * \cdots * a^{c_0 * 2^0}\]

因为 $k = \lceil{\log_2(b + 1)}\rceil$ ，所以上式乘积项的数量不多于 $\lceil{\log_2(b + 1)}\rceil$ 个。

又因为：

\[a^{2^i} = (a^{2^{i - 1}})^2\]

所以很容易通过 $k$ 次递推求出每个乘积项，当 $c_i = 1$ 时，把该乘积项累积到答案中。

• b&1 运算可以取出 $b$ 在二进制表示下的最低位
• b>>1 运算可以舍去最低位

在递推的过程中将二者结合，就可以遍历 $b$ 在二进制表示下的所有数位 $c_i$ 。

在循环到 $i$ 次时，变量 $a$ 中存储的是 $a^{2^i}$，若 $b$ 该位为 $1$，则把此时的变量 $a$ 累计到答案 ans 中。

在 C++ 语言中，两个数值执行算数运算时，以参与运算的最高数值类型为基准，与保存结果的变量类型无关。

虽然两个 32 位整数的乘积可能超过 int 类型的表示范围，但是 CPU 只会用 1 个 32 位寄存器保存结果，造成越界现象。

因此，我们必须把其中一个数强制转换成 64 位整数类型 long long参与运算，从而得到正确的结果。

最终对 $p$ 取模以后，执行赋值操作时，该记过会被隐式转换成 int 存回 ans 中。

整个算法的时间复杂度为 $\mathcal{O}(\log_2b)$。

完整代码：a^b.cpp