# 快速幂

快速幂，又叫欧拉降幂。它的作用也很简单，就是快速的求出$a^k \bmod p$ 的值。

# 问题

给出 n 组数 $a, k, p$ ，每组数据都求出 $a^k \bmod p$ 的值是多少。

# 数据范围

$1 \le n \le 100000$
$1 \le a,k,p \le 2 * 10^9$

# 分析

从问题出发。因为 a 和 k 的范围都很大，最大可以到 $2 * 10^9$ 。所以，比较容易想出来的做法是为了避免高精度计算，可以根据同余定理，边乘边取模。（ 同余 非本文内容，此处就不深入展开啦～）

res = 1

for i in range(k):

    res = res * a % p

但是，这种做法的时间复杂度是$O(k)$ ，而 k 的取值最大也会到 $2 * 10^9$ 。妥妥的超时。

# 快速幂（欧拉降幂）

而使用快速幂可以把时间复杂度优化到 $O(log_k)$ ，即便 k 取到了最大值，也只需要循环 30 次左右，极大的提高了计算速度。

# 核心思路

# 一。拆分$a^k \bmod p$

拆分依赖一个重要的知识点 乘除法指数运算方法 ：在乘除法的指数运算中，同底数幂相乘，底数不变，指数相加；同底数幂相除，底数不变，指数相减。

用公式表示为：

$$a^n*a^m=a^{n+m}$$

$$a^n\div{a^m}=a^{n-m}$$

如何拆分呢？

1. 我们可以把 k 拆分成二进制的表示形式。使用二进制来表示一个比较大的数，这种技巧我们在其他地方也多有应用，比如多重背包的二进制优化，状态压缩 DP。

   举例：当前 k=11 ，我们可以把 k 拆分成$11=(1011)_2$ 。

2. 现在，想一下把二进制还原成十进制是怎么做的？一般使用早就学过的 “按位记数法”。即，从低位到高位，列出 2 的指数幂，指数从 0 开始，每右移一位指数就加一，当前位若是 1 就累加起来，最后的结果就是十进制。

   举例：当前二进制是 $11=(1011)_2$ ，那么按照 “按位记数法” 的展开公式就是 $1 * 2^0 + 1 * 2 ^ 1 + 0 * 2^ 2 + 1 * 2 ^ 3$，最后计算结果为 11 。

3. 假设$k=2^0+2^1+2^2+...+2^x$，那么根据乘除法指数运算方法，$a^k$ 可以写成 $a^{(2^0+2^1+2^2+...+2^x)}$ 。

4. 继续推导，上述公式又可以写成 $a^{2^0}*a^{2^1}*a^{2^2}*...*a^{2^x}$ 的形式。

5. 这一步最大可以分解出的指数是$log(k)$ ，也就是 x 的取值范围最大是$log(k)$ 。

现在，经过一番推导后，我们发现只要计算最终的那个公式就可以计算出 $a^k$ 。

# 二。预处理数据

我们可以把最终公式中的数据（$a^{2^0}$,$a^{2^1}$,$a^{2^2}$,...,$a^{2^x}$）都预处理出来，这样计算的时候就可以直接用。

1. 其中第一个数 $a^{2^0}$ 的值就是 a 本身；

2. 而 $a ^ { 2 ^ 1 }$ 可以写成$a ^ { 2 ^ 1 } = a ^ { { 2 ^ 0 } * 2 } = ( a ^ { 2 ^ 0 }) ^ 2$；

3. 以此类推，$a^{2^2}$ 可以写成 $a^{2^2}=(a^{2^1})^2$。

4. 最终找到以下规律:

   $$\begin{array}{c} a ^ { 2 ^ 0 } = a \\ a ^ { 2 ^ 1 } = ( a ^ { 2 ^ 0 } ) ^ 2 \\ a ^ { 2 ^ 2 } = ( a ^ { 2 ^ 1 } ) ^ 2 \\ \vdots \\ a ^ { 2 ^ x } = ( a ^ { 2 ^ { x - 1 } } ) ^ 2 \\ \end{array}$$

也就是说预处理数据中，下面的每一项都是上一项的平方。这里 x 的取值与上面相同，也是$log(k)$ 。

# 举例

当前$a=4,k=5,p=10$ ，此时有$4^5\bmod10=4$。

我们用快速幂的方式，计算上面结果。

1. 拆分 k 。$k=5=(101)_2$ ；

2. 二进制计算十进制。$(101)_2=1*{2^0} + 0 * {2^1} + 1 * {2^2}=5$ ;

3. 代入到$4^5 \bmod 10=4^{(2^0+2^2)} \bmod 10$ ，分解一下上面公式，得到$4^{(2^0)} * 4^{(2^2)} \bmod 10$。

4. 预处理数据。为避免计算中数据过大，根据同余定理，在计算过程中对每一步都进行取模运算：

   $$\begin{array}{c} 4^{2^0}=4 \bmod 10 = 4\\ a^{2^1}=(a^{2^0})^2 = 16 \bmod 10 =6\\ a^{2^2}=(a^{2^1})^2 = 36 \bmod 10 = 6\\ \end{array}$$

5. 预处理结果代入到公式：
   $4^{(2^0)} * 4^{(2^2)} \bmod 10=4*6=24\bmod 10=4$

6. 得到最终结果：$4^5\bmod10=4$ 。

# Code

实现上，边计算最终结果边处理数据。每组数据的时间复杂度是$O(logk)$，总共 n 组数据，总时间复杂度是$O(nlogk)$ 。

#include <iostream>

using namespace std;

typedef long long LL;

LL pow(int a, int k, int p) {

    LL res = 1 % p;

    while (k) {

        // 当前 k 的二进制为是 1，则计算结果

        if (k & 1) res = res * a % p;

        // 反复平方 预处理数据

        a = a * (LL)a % p;

        // 从低位到高位进行计算。

        k >>= 1;

    }

    return res;

}

int main() {

    int n;

    scanf("%d", &n);

    while (n -- ) {

        int a, k, p;

        scanf("%d%d%d", &a, &k, &p);

        printf("%lld\n", pow(a, k, p));

    }

    return 0;

}

END