跳转至

快速幂

递归的方法实现

//LeetCode 50
#include <cmath>
class Solution {
public:
    double myPow(double x, long long n) {
        if(n == 0) return 1.0;
        if(n == 1) return x;
        if(n == -1) return 1.0 / x;

        if(n % 2 == 0) {
            double res = pow(x, n / 2);
            return res * res;
        }
        else {
            double res = pow(x, (n - 1) / 2);
            return res * res * x;
        }    
    }
};

非递归的实现：

#include <cmath>
class Solution {
public:
    double myPow(double x, long long n) {
        if(n == 0) return 1.0;

        if (n < 0) {
            x = 1.0 / x;
            n *= -1;
        }
        double res = 1;
        while (n != 0) {
            if (n & 1) res = res * x;
            x = x * x;
            n >>= 1;
        }
        return res;
    }
};

矩阵快速幂

OI Wiki的应用总结：

  • 模意义下取幂
  • 计算斐波那契数（可以和卡特兰数结合）
  • 多次置换
  • 加速几何中对点集的操作
  • 定长路径计数
  • 模意义下的大整数乘法
  • 高精度快速幂

https://oi-wiki.org/math/quick-pow/

矩阵快速幂等

典型题目：