快速幂的模板

例题：数值的整数次方

原题链接：力扣16
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xⁿ）。不得使用库函数，同时不需要考虑大数问题。

示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

提示：
-100.0 < x < 100.0
-2³¹<= n <= 2³¹-1
-10⁴<= xⁿ<= 10⁴

思想：

xⁿ实际上可以转换成如下所示：

n的二进制表示为：b_m…b₃b₂b₁，即n=2^b1+2^b2+…+2^bm；

xⁿ=x^bm…b3b2b1=x^bm * …*x^b3 * x^b2 * x^b1；

所以我们只需要把n的二进制表示分解出来，就可以表示出xⁿ；

例如：2¹⁰=2²⁺⁸=2² * 2⁸；

模板：

    public double myPow(double x, int n) {
    if(x==0) return x;
    long b=n;//因为n有可能等于-2^31^在n=-n时会溢出，所以用long b来接受,之后再执行b=-b;
    if(b<0){
        b=-b;
        x=1/x;
    }
    double res=1;
    while(b>0){
    if((b&1)==1){//如果b的对应二进制位为1，则让res*x；
        res*=x;
    }
    b=b>>1;//遍历b的二进制位
    x*=x;//让x等于对应二进制位的值，如当10遍历到4个二进制位时（从右往左数）x=x^3^,每次遍历都让它自乘就可以达到这种效果；
    }
    return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

应用题：快速幂

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

输入格式
第一行包含整数 n。
接下来 n 行，每行包含三个整数 ai,bi,pi。

输出格式
对于每组数据，输出一个结果，表示 ai^bi mod pi 的值。
每个结果占一行。

数据范围
1≤n≤100000,
1≤ai,bi,pi≤2×10⁹
输入样例：
2
3 2 5
4 3 9
输出样例：
4
1

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        for(int i=0;i<n;i++){
            int a=sc.nextInt();
            int b=sc.nextInt();
            int p=sc.nextInt();
            int res=1%b;
            while(b>0){
               if(b%2==1) res = (int)((long)res*a%p);
                a = (int)((long)a*a%p);
                b=b>>1;
            }
            System.out.println(res);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19