快速幂和矩阵快速幂

快速幂,顾名思义就是快速求幂的算法。原理如下:

假设求 a 的 n 次方,当 n 为偶数时,a 的 n 次方可以由两个 a 的 n/2 次方相乘求得;当 n 为奇数时,a 的 n 次方可以由两个 a 的 n/2 次方相乘的积再乘以 a 得到。

在实现中,运用位运算判断奇偶和乘除 2(第一个想到的简直就是天才)

#include <iostream>
using namespace std;
double quick_pow(double base,int degree) {
    double ans = 1.0;
    while (degree) {
        if (degree&1)
            ans *= base;
        base *= base;
        degree >>= 1;
    }
    return ans;
}
int main() {
    double a;
    int b;
    cin>>a>>b;
    cout<<quick_pow(a,b)<<endl;
}

矩阵快速幂呢,则是把求幂的对象变成了矩阵,下面是一道经典应用。

#include <iostream>
using namespace std;
int N = 10000,n;
void Matrix(int (&a)[2][2],int b[2][2]){
    int tmp[2][2] = {0};
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j)
            for(int k = 0; k < 2; ++k)
                tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % N;
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j)
            a[i][j] = tmp[i][j];
}
int main(){
    while(cin>>n && n!=-1){
        int temp[2][2] = {1, 1, 1, 0},cot[2][2] = {1, 0, 0, 1};
        while(n){
            if(n & 1) Matrix(cot,temp);
            Matrix(temp,temp);
            n /= 2;
        }
        cout<<cot[0][1]<<endl;
    }
}

这个 的应用就很考数学功底,知道原理就好。