题目描述

有n次操作，每次输入a,b,p，请你计算：$$a^b\quad mod\quad p$$

其中
$0<a,b,p<10^9$
$0<n<10^5$

样例

输入

2
3 2 5
4 3 9

输出

4
1

误区

1.直接使用函数求出幂后再做模运算：数字太大会溢出
2.使用for循环，利用数学公式积的模=模的积进行计算解决数字太大问题：时间复杂度为o(b),由于题目中给出的b范围较大，会造成时间复杂度过大。

解决方法

快速幂

举个栗子$$a^5=a^{(101)_2}$$
$$a^{(101)_2}=a^{2^0}*a^{2^2}$$

即我们可以将$$a^b\Rightarrow \prod a^{2^n}$$

过程
1.过程中处理出
$$\lbrace a^{2^0} \quad a^{2^1} \ldots a^{2^{\log b}} \quad \rbrace$$
2.b进行移位操作，判断当前位是否为1，为1则对应乘上当前位$a^{2^n}$然后模p

C++ 代码

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

⭐
因为在循环中涉及到b的移位操作，所以该算法的时间复杂度为o(log b)