登录
← 返回首页 | 代码片段 › 1 基础算法 › 1.3 快速幂 › 快速幂 / 搜索
JSON MD

1.3 快速幂

快速幂 binpow
9 行
CPP JSON
【快速幂(二分幂)——无 MOD 版】 ▪ binpow(a, b) — 计算 a^b,将指数按二进制拆分:b 的最低位为 1 时乘入结果;a 不断自乘;b 每次右移一位。 时间复杂度 O(log b),空间 O(1)。注意无取模时结果可能溢出(b 较大时需要高精度或换用带 MOD 版)。
C++ 9 行 CPP
long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
快速幂带MOD binpow-mod
9 行
CPP JSON
【快速幂(二分幂)——带 MOD 版】 ▪ binpow(a, b) — 计算 a^b % MOD,在每次乘法后取模防止中间结果溢出。算法流程:res=1;b>0 时若 b&1 则 res=res*a%MOD;a=a*a%MOD;b>>=1。 时间复杂度 O(log b),空间 O(1)。适用于大数幂取模(RSA 加密、组合数取模、哈希计算等)。
C++ 9 行 CPP
long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res % MOD;
}
矩阵快速幂 mksm
30 行
CPP JSON
【矩阵快速幂(mksm)】 代码包含 qpow 等核心函数,实现了 矩阵快速幂 的算法逻辑。 核心函数: Matrix qpow(Matrix a,int b) — 快速幂 核心结构体:Matrix 关键配置: N=3,mod=1e9+7
C++ 30 行 CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=3,mod=1e9+7;
struct Matrix{
	int mat[N][N];
	Matrix(){memset(mat,0,sizeof(mat));}
	Matrix operator*(const Matrix& o)const{
		Matrix res;
		for(int i=0;i<N;++i){
			for(int k=0;k<N;++k){
				for(int j=0;j<N;++j){
					res.mat[i][j]=(res.mat[i][j]+mat[i][k]*o.mat[k][j])%mod;
				}
			}
		}
		return res;
	}
};

Matrix qpow(Matrix a,int b){
	Matrix res;
	for(int i=0;i<N;++i)res.mat[i][i]=1;
	while(b){
		if(b&1)res=res*a;
		a=a*a;
		b>>=1;
	}
	return res;
}
已复制