数据结构学习 快速幂

看了这一篇很好的文章：快速幂，学习了一下快速幂。如果你看到这篇文章想要学习快速幂，我建议你直接去看这篇文章吧，下面的都是我个人的笔记和碎碎念。

重拾我的考研线性代数，非常有趣呢！

?基本的快速幂：

递归快速幂：

根据上面那张图，很容易写出递归快速幂的代码。

注意1：分0，奇数，偶数
注意2：为了防止溢出，取模，long long

#include <iostream>
#define MOD 1000000007//取模
//递归快速幂
//注意1：分0，奇数，偶数
//注意2：为了防止溢出，取模，long long
int qpow(int a, int n)//a^n
{
	if (n == 0)
		return 1;
	if (n & 1)//奇数
		return a * qpow(a, n - 1) % MOD;
	else//偶数
	{
		long long temp = qpow(a, n / 2) % MOD;
		return temp * temp % MOD;
	}
}

void Test_qpow1()
{
	int a = 2, n = 0;
	std::cout << "a: " << a << " n: " << n << " result: " << qpow(a, n) << std::endl;
	a = 2;
	n = 4;
	std::cout << "a: " << a << " n: " << n << " result: " << qpow(a, n) << std::endl;
	a = 2;
	n = 501;
	std::cout << "a: " << a << " n: " << n << " result: " << qpow(a, n) << std::endl;
}

非递归快速幂：

别人的写法：

这个就比较难了。利用的是将n化为二进制，用二进制的10来控制是否要乘入。

具体来看上面提到的那篇文章说的吧...：

模仿着写了一遍（弱弱地）?

#define MOD 1000000007//取模
//这是在网上看见的 比我写的好 但是有点难理解
//用了二进制
int qpow2(long long a, int n)//a^n
{
	long long mul = 1;
	while (n)//二进制，比如5：101，在1的时候才乘进来
	{
		if (n & 1)
			mul = mul * a;
		n>>=1;
		a = a * a;//这里在累计
	}
	return mul;
}

我写的：

我在看上面那篇文章提供的非递归快速幂之前，自己尝试写的非递归快速幂。写完虽然能跑，但是看上去有点low哦...

非常直白的for循环，因为只要循环logn次，所以我直接求对数了！和上面的基本不一样的。其实还是用的和上面的递归一样的思想做的，但是被我生生弄成非递归了哈哈...

#include <iostream>
#include <cmath>
#define MOD 1000000007//取模
//非递归快速幂
//注意1：分0，奇数，偶数
//注意2：为了防止溢出，取模，long long
//这是我写的 有点愚蠢 用了求对数
int qpow1(int a, int n)//a^n
{
	if (n == 0)
		return 1;
	if (n == 1)
		return a;
	long long mul = a;
	if (n & 1)//奇数
	{
		for (int i = 0; i < log2(n - 1); ++i)//取对数
		{
			mul = mul * mul % MOD;
		}
		mul = mul * a % MOD;//因为是奇数所以得补一个
	}
	else//偶数
	{
		for (int i = 0; i < log2(n); ++i)
		{
			mul = mul * mul % MOD;
		}
	}
	return mul;
}

?矩阵快速幂：斐波那契数列

用的是非递归快速幂模板套进去的，太帅了！

再次重申，看我的代码不如看上面那篇。那位大哥写的真好，我也要反复看！

注意1：斐波那契数列的矩阵公式推导，我觉得要自己推一次，非常简单的矩阵公式。
注意2：单位矩阵和斐波那契的矩阵

里面还有矩阵的写法，学到了！

#include <iostream>
#define MOD 1000000007//取模
//矩阵快速幂
//注意1：斐波那契数列的矩阵公式推导
//注意2：单位矩阵和斐波那契的矩阵
struct matrix//矩阵对象
{
	long long a1, a2, b1, b2;
	matrix(long long a1, long long a2, long long b1, long long b2) :a1(a1), a2(a2), b1(b1), b2(b2) {}
	matrix operator*(const matrix& y)//两个矩阵相乘
	{
		matrix ans(
			(a1 * y.a1 + a2 * y.b1) % MOD,
			(a1 * y.a2 + a2 * y.b2) % MOD,
			(b1 * y.a1 + b2 * y.b1) % MOD,
			(b1 * y.a2 + b2 * y.b2) % MOD
			);
		return ans;
	}
};
matrix qpow(matrix a, int n)//a^n	
{
	matrix ans(1, 0, 0, 1);//是单位矩阵
	//|1  0|
	//|0  1|
	while (n)
	{
		if (n & 1)
			ans = a * ans;
		a = a * a;
		n >>= 1;
	}
	return ans;
}

void Test_qpow3()
{
	int n = 6;
	matrix M(0, 1, 1, 1);//注意这里是斐波那契数列推导的矩阵
	long long result;
	if (n != 0)
	{
		matrix ans = qpow(M, n - 1);//这里求的是M^(n-1)：底数是M，幂是n-1
		 result = (ans.a1 + ans.a2) % MOD;//求的是F(n)
	}
	else
		result = 0;
	std::cout << result << std::endl;
}