快速幂的那些小事儿

快速幂

众所周知，C++中提供了pow函数方便计算一个数的幂次方，那此时，就需要一个一个底数往上乘

此时时间复杂度为$O(n)$的时间复杂度，那么有没有更快的的办法呢？快速幂可以压缩到$O(logn)$

快速幂是根据其二进制完成时间复杂度的压缩

对于任意一个数，可以将他化为二进制，那么此时他的每一位就变成了0或者1

 n = 10010101

1	0	0	1	0	1	0	1
128	64	32	16	8	4	2	1

即n等于每一位的2的幂次然后如果为1那就加上，如果为零，那就不加

#include<iostream>

using namespace std;

#define ll long long

const int N = 2e5 + 10, M = 200010;

int qpow(int a,int b)
{
    int r = 1;
    while(b)
    {
        if(b&1) r *= a;
        a *= a;
        b >>= 1;
    }
    return r;
}

void solve()
{
    int n, k;
    cin >> n >> k;
    cout << qpow(n, k) << '\n';
}
int main()
{   
    int t = 1;  // cin >> t;
    while(t --)
    {
        solve();
    }
    return 0;
}

矩阵快速幂

斐波那契数列

$f(n)=f(n - 1) + f(n - 2)$

可得出 0 1 1 2 3 5 8 13 ….. ,如果将其两两配对变成<0,1>,<1,1>,<1,2>,<2,3> ….

且通过可以通过快速幂对这个过程进行优化

代码如下:

其中需要一个单位矩阵，作为快速幂运算中的1的替代

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

#define ll long long
#define th this

const int N = 1e5 + 10;
const int rc = 2;
const int MOD = 1e9 + 7;

struct matrix{
	int matr[2][2];
	matrix(){memset(matr,0,sizeof matr);};
	// operator
	matrix operator*(matrix b)
	{
		matrix a;
		for(int i = 0;i < rc;i ++)
			for(int j = 0;j < rc;j ++)
				for(int k = 0;k < rc;k ++)
					a.matr[i][j] += 1ll * th->matr[i][k] * b.matr[k][j];
		return a;
	}
};

matrix qpow(matrix a,int b)
{
	matrix r;

	r.matr[0][0] = r.matr[1][1] = 1;

	while(b)
	{
		if(b&1) r = r * a;
		a = a * a;
		b >>= 1;
	}
	return r;
}

void solve()
{
	int n;
	matrix a;
	a.matr[0][1] = a.matr[1][0] = a.matr[1][1] = 1;
    
	cin >> n;
    
	matrix tt = qpow(a, n);

	cout << tt.matr[0][0] << '\n';
}

int main()
{   
    int t = 1; //cin >> t;
    while(t --)
    {
        solve();
    }
    return 0;
}