快速幂

• 0. 概述
• 1. 应用一、幂取余：计算 $a^n(mod\ m)$
• 2. 应用二、计算斐波那契数列的第n项【矩阵快速幂】
• 3. 应用三、将线性变换重复 $n$ 次【矩阵快速幂】
• 4. 应用四、极斐波那契【矩阵快速幂+龟速乘】

0. 概述

• 关键在于把a的n次方中的n拆分成二进制的表示形式

• 对于 $n$ 的二进制，我们从低到高不断遍历每一位，如果遍历到的那一位是 $1$ ，就 $r×a$

• 伪代码中的 $n(mod\ 2)$ 可以用 $n&1$ 来表示，$n=floor(n/2)$ 也可以用无符号右移一位来表示，即 $n>>2$

1. 应用一、幂取余：计算 $a^n(mod\ m)$

• 只需要在快速幂算法中合适的位置上加上 $mod\ m$，即可得到幂取模的代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
// 计算a的n次方模m
int ModExpFast(int a,int n,int m) {
	int res;
	a=a%m;
	res=1; // 乘法操作的初始值(累积变量)
	while(n!=0) {
		if(n%2==1) {
			res=(res*a)%m;
		}
		a=(a*a)%m;
		n=n>>1;
	}
	return res; // 得到最终的余数
}
signed main() {
	int a,n,m;
	cin>>a>>n>>m;
	cout<<a<<"^"<<n<<" mod "<<m<<"="<<ModExpFast(a,n,m);
	return 0;
}

• 幂取模运算在密码学和数论中有着非常重要的应用，比如，幂取模运算是RSA公钥加密的核心运算之一。

2. 应用二、计算斐波那契数列的第n项【矩阵快速幂】

• 以上是适用于矩阵快速幂的数据范围

• 只需要计算出 $[1\ 1; 1\ 0]$ 的 $n$次方和已知 $F0$ 与 $F1$，就可以计算出第 $n$ 项

• 以下是一个利用矩阵快速幂计算第 $n$ 项并维护前 $n$ 项和的矩阵快速幂模板

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;

// 题目描述: 矩阵快速幂求斐波那契数列,[fn, fn+1] × [0 1; 1 1]= f[n+1, fn+2]
// 这道题还要求斐波那契数列前n项的和,所以除了fn以外还需要维护Sn
// [fn, fn+1, sn] × [0 1 0; 1 1 0; 0 1 1] = f[n+1, fn+2, sn+1]

const int N=3; // 矩阵3×3
int n,m; // 本题要求计算出前n项和mod m的值

// 一维×二维两重循环,c=a*b
void mul(int c[],int a[],int b[][N]) {
	int temp[N]={0};
	for(int i=0;i<N;i++) {
		for(int j=0;j<N;j++) {
			temp[i]=(temp[i]+(ll)a[j]*b[j][i])%m;
		}
	}
	// 注意:传进来的指针和本身的指针有区别(形参),如果这里sizeof c
	// 传回来的是指针的长度,而不是数组的长度,所以sizeof temp
	memcpy(c,temp,sizeof temp);
}

// 二维×二维三重循环,c=a*b
void mul(int c[][N],int a[][N],int b[][N]) {
	int temp[N][N]={0};
	for(int i=0;i<N;i++) {
		for(int j=0;j<N;j++) {
			for(int k=0;k<N;k++) {
				temp[i][j]=(temp[i][j]+(ll)a[i][k]*b[k][j])%m;
			}
		}
	}
	memcpy(c,temp,sizeof temp);
}

int main() {
	cin>>n>>m;
	int f1[N]={1,1,1}; // f1,f2,s1;存储答案,f1[2]就是Sn
	// 推导出来的幂矩阵
	int a[N][N]= {
		{0,1,0},
		{1,1,1},
		{0,0,1}
	};
	// 计算f1×a^n
	// 迭代计算,类似于滚动数组,没有利用额外的空间
	n--; // 调整斐波那契数列的起始位置
	// 快速幂思想
	while(n) {
		if(n&1) mul(f1,f1,a); // res=res*a,调用一维矩阵×二维矩阵的mul方程
		mul(a,a,a); // a=a*a,调用二维矩阵×二维矩阵的mul方程
		n>>=1;
	}
	cout<<f1[2]<<endl;
	return 0;
}

3. 应用三、将线性变换重复 $n$ 次【矩阵快速幂】

4. 应用四、极斐波那契【矩阵快速幂+龟速乘】

• 对我来说有难度，暂时不上代码

打赏