在做幂运算时，根据计算机做乘法运算的原理，我们可以选择快速幂来优化运算。

题目

分析

若b很大，就容易爆数据，例如下面这种情况，不过如果只是想拿到40%的分值，这种使用循环语句求幂乘的方法就可以应付了。

下面正式介绍快速幂。
原理： 使用二进制将指数转换为2的幂次和相加，从而使得时间复杂度从O(n)降低到O(log n)。

假设b=10，10用二进制表示为1010,请回忆，我们在转换二进制为十进制时是这样的：2³*1+2²*0+2¹*1+2⁰*0=10,
从而就可以有a^b=a^ (2³*1+2²*0+2¹*1+2⁰*0)=[a^ (2³*1)] *[ a^ (2²*0)] * [a^ (2¹*1)] * [a^ (2⁰*0)]
等式右边从右往左数奇数项均为1（a⁰=1),也就是如果按照二进制的解法来求幂乘，便不需要考虑二进制为0的位。事实上在求的是：a^ (2ⁿ )的累乘，其中n是二进制展开式中不为0的位。

代码如下：

import java.util.*; 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long a = scanner.nextInt();  //a不能定义为int型，因为a在后面会涉及到做乘法
        int b = scanner.nextInt();
        int p = scanner.nextInt();
        long res = 1L;            //1转换为long 再赋值给res
        while (b > 0) {          //1010
            if ((b & 1) == 1) {  //判断经过上一次的循环之后，当前最右边的位上是1还是0
                res = res * a % p;   //是1就要乘进来
            }
            a= a * a % p;          //用于记录每一位所对应的a^(2^n),a(2^3)、a(2^2)、a(2^1)、a(2^0),而上面的if判断决定要不要乘
            b >>= 1;             //1010向右挪动一位变成101
        }
        res %= p;
        System.out.println(res);
    }
}

补充：一边做乘法一边取余和全部相乘再取余结果是一致的，读者可自行证明。

运行结果：

这样就可以拿到全分了！