# 题目描述

给定 $n$ 组 $a_i,b_i,p_i$，对于每组数据，求出 $a_i ^ {b_i}$ $mod$ $p_i$ 的值

# 算法思路

对于数 $a_i ^ {b_i}$ $mod$ $p_i$ 有，$b_i$ 可以拆成二进制表示
以 $4^5$ $mod$ $10$ 为例
$5$ 的二进制表示为 $101$

$$\Large\color{red}{4^5 = 4^{2^0} * 4^{2^2}}$$

不断取出 $b_i$ 的最后一位，在取的过程中，$a$ 不断平方

1
2
3
4
5
6
7
8
9

int qmi(int a, int b, int p) {
    int res = 1;
    while(b) {
        if(b & 1)
            res = res * a % p;
        b >>= 1, a = a * a % p;
    }
    return res;
}