$$\color{Red}{快速幂}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

给定 n 组 ai,bi,pi，对于每组数据，求出ai ^ (bi) % pi 的值。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含三个整数 ai,bi,pi。

输出格式

对于每组数据，输出一个结果，表示 ai ^ (bi) % pi 的值。

每个结果占一行。

数据范围

1 ≤ n ≤ 100000

1 ≤ ai, bi, pi ≤ 2 × 10 ^ 9

输入样例：

2
3 2 5
4 3 9

输出样例：

4
1

证明

暴力做法：

显然我们只需要进行 bi 次迭代即可完成这项工作。

public class Main {

    static int n, a, b, p;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        while(n -- > 0){
            String [] s = br.readLine().split(" ");
            a = Integer.parseInt(s[0]);
            b = Integer.parseInt(s[1]);
            p = Integer.parseInt(s[2]);
            long res = 1;
            while (b -- > 0){
                res = res * a % p;
            }
            System.out.println(res);
        }
    }
}

如何进行优化？——> 学过多重背包就知道我们的老朋友 二进制分堆

多重背包:三种语言+(迭代版和物理版)二进制分堆

我们把枚举b次 换成log(k)次，分堆为

a ^ (2^0),a ^ (2^1) ...... a ^ (2^log(b))

而为了表示出我们的 a ^ b 只需要进行选取相乘，根据二进制组合必能表示出对应的数字

二进制分堆版

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int n, a, b, p;

    static long qmi(long a, int b, int p) {
        long res = 1;
        while (b > 0) {
            // 目前最低位为 1 就要把这位的a（已经被处理成当前为1的次方数了）
            if ((b & 1) == 1) res = res * a % p;
            // 不管这位是否为 1 都需要右移
            b >>= 1;
            // 每次循环都需要把 a 预处理
            a = a * a % p;
        }
        return res;
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        while (n-- > 0) {
            String[] s = br.readLine().split(" ");
            a = Integer.parseInt(s[0]);
            b = Integer.parseInt(s[1]);
            p = Integer.parseInt(s[2]);
            long res = qmi(a, b, p);
            System.out.println(res);
        }
    }
}