跳至主要內容

快速幂

2023年12月17日大约 2 分钟

快速幂

题目难度
50. Pow(x, n)中等模板题
70. 爬楼梯简单矩阵快速幂
509. 斐波那契数简单矩阵快速幂
1137. 第 N 个泰波那契数简单矩阵快速幂

模板

快速幂取模（当数很大时，相乘 long long 也会超出的解决办法）

import java.nio.charset.StandardCharsets; import java.util.Scanner;  public class Abc293_e {  public static void main(String[] args) {  Scanner scanner = new Scanner(System.in, StandardCharsets.UTF_8);  int A = scanner.nextInt();  long X = scanner.nextLong();  int M = scanner.nextInt();  System.out.println(solve(A, X, M));  }   private static String solve(int A, long X, int M) {  if (A == 1) {  return String.valueOf(X % M);  }  long mod = M * (A - 1L);  long x = quickPow(A, X, mod) - 1;  x /= (A - 1);  x = (x + M) % M;  return String.valueOf(x);  }   private static long quickPow(long a, long b, long m) {  long res = 1L;  while (b > 0) {  if ((b & 1) == 1) {  res = multi(res, a, m);  }  a = multi(a, a, m);  b >>= 1;  }  return res;  }   // a * b % m  // 快速幂取模（当数很大时，相乘 long long 也会超出的解决办法）  private static long multi(long a, long b, long m) {  long res = 0L;  while (b > 0) {  if ((b & 1) == 1) {  res = (res + a) % m;  }  a = (a + a) % m;  b >>= 1;  }  return res;  } }

50. Pow(x, n)

public class Solution50 {  public double myPow(double x, int n) {  if (n >= 0) {  return quickPow(x, n);  }  return 1.0 / quickPow(x, -(long) n);  }   private double quickPow(double x, long pow) {  double ans = 1.0;  while (pow > 0) {  if (pow % 2 == 1) {  ans *= x;  }  x *= x;  pow /= 2;  }  return ans;  } }

矩阵快速幂

70. 爬楼梯

public class Solution70 {  public int climbStairs(int n) {  int[][] mat = {{1, 1}, {1, 0}};  int[][] mPowN = matQuickPow(mat, n);  int[] f = {1, 1};  return getFn(f, mPowN);  }   // 矩阵快速幂 res = f(n)  private int getFn(int[] f, int[][] mPowN) {  int len = f.length;  int res = 0;  for (int i = 0; i < len; i++) {  res += mPowN[len - 1][i] * f[len - 1 - i];  }  return res;  }   // 矩阵快速幂 res = a^n  private int[][] matQuickPow(int[][] a, int n) {  int len = a.length;  // 对角矩阵  int[][] res = new int[len][len];  for (int i = 0; i < len; i++) {  res[i][i] = 1;  }  while (n > 0) {  if ((n & 1) == 1) {  res = matMulti(res, a);  }  n >>= 1;  a = matMulti(a, a);  }  return res;  }   // 矩阵快速幂 res = a * b  private int[][] matMulti(int[][] a, int[][] b) {  int len = a.length;  int[][] res = new int[len][len];  for (int i = 0; i < len; i++) {  for (int j = 0; j < len; j++) {  for (int k = 0; k < len; k++) {  res[i][j] += a[i][k] * b[k][j];  }  }  }  return res;  } }

509. 斐波那契数

public class Solution509 {  public int fib(int n) {  int[][] mat = {{1, 1}, {1, 0}};  int[][] mPowN = matQuickPow(mat, n);  int[] f = {0, 1};  return getFn(f, mPowN);  }   // ··· }

1137. 第 N 个泰波那契数

public class Solution1137 {  public int tribonacci(int n) {  int[][] mat = {{1, 1, 1}, {1, 0, 0}, {0, 1, 0}};  int[][] mPowN = matQuickPow(mat, n);  int[] f = {0, 1, 1};  return getFn(f, mPowN);  }   // ··· }

（全文完）