计算 x``n 其中n为正整数
若n为负数，考虑转换成 1.0 / x ``(-n)

思路：将指数n转换成二进制形式
例如 x = 3, n = 7
其中n转换成二进制形式为 0111
`x= 3 = 3``= 3 3```` 3```

  1. public double calPow(double x, long n) {
  2.     //数学方法，将指数分解为二进制形式，根据1所在位逐一计算
  3.     //result用于记录结果
  4.     double result = 1.0;
  5.     //x_per用于倍增
  6.     double x_per = x;
  7.     while (n > 0) {
  8.         if ((n & 1) != 0) {
  9.             result *= x_per;
  10.         }
  11.         x_per *= x_per;
  12.         n >>= 1;
  13.     }
  14.     return result;
  15. }

例题

875. 快速幂
给定 n 组 ai,bi,pi，对于每组数据，求出 aibimodpi 的值。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含三个整数 ai,bi,p。
输出格式
对于每组数据，输出一个结果，表示 aibimodpi 的值。
每个结果占一行。
数据范围
1≤n≤100000,
1≤ai,bi,pi≤2×109
输入样例：

  1. 2
  2. 3 2 5
  3. 4 3 9

输出样例：

  1. 4
  2. 1

时间复杂度 O(log b)

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  7.         int n = sc.nextInt();
  8.         while (n-- > 0) {
  9.             int a = sc.nextInt(), b = sc.nextInt(), p = sc.nextInt();
  11.             int ans = qmi(a, b, p);
  13.             System.out.println(ans);
  14.         }
  15.     }
  17.     static int qmi(long a, int b, int p) {
  18.         long res = 1;
  20.         while (b > 0) {
  21.             if ((b & 1) == 1) {
  22.                 res = res * a % p;
  23.             }
  24.             a = a * a % p;
  25.             b >>= 1;
  26.         }
  27.         return (int) res;
  28.     }
  29. }

注意溢出问题