快速幂

• OI Wiki: https://oi-wiki.org/math/quick-pow/

题目	难度
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);
    }

    // ···
}

（全文完）