【费马小定理降幂+矩阵快速幂+快速幂】M斐波那契数列 HDU - 4549

桃扇骨 2022-06-07 11:26 166阅读 0赞

Think:  
1知识点：费马小定理降幂+矩阵快速幂+快速幂  
（１）：费马小定理降幂：  
定理：若gcd(A, M) == 1，则A^x = A^(x%Eular(M))(mod M)  
注：Eular(M)为M的欧拉函数值  
2题意：  
已知：  
F\[0\] = a  
F\[1\] = b  
F\[n\] = F\[n-1\] \* F\[n-2\] ( n > 1 )  
输入a, b, n，询问F\[n\] = ?  
3解题方法：  
（１）：  
F\[0\] = a  
F\[1\] = b  
F\[2\] = b\*a  
F\[3\] = b^(2)\*a  
F\[4\] = b^(3)\*a^(2)  
F\[5\] = b^(5)\*a^(3)  
.  
.  
.  
F\[n\] = b^(fib(n-1))\*a^(fib(n-2))  
（２）：由于快速幂指数太高，因此需要通过费马小定理降幂

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    const int mod = 1000000007;
    
    struct Matrix{
        LL v[4][4];
    };
    
    Matrix multiply(const Matrix &a, const Matrix &b, int Matrix_len);
    Matrix matrix_pow(Matrix &x, int k, int Matrix_len);
    LL num_pow(LL num, LL k);
    
    int main(){
        LL a, b;
        int n;
        while(~scanf("%lld %lld %d", &a, &b, &n)){
            if(n == 0){
                printf("%lld\n", a%mod);
                continue;
            }
            if(n == 1){
                printf("%lld\n", b%mod);
                continue;
            }
            Matrix x;
            x.v[0][0] = 1, x.v[0][1] = 1;
            x.v[1][0] = 1, x.v[1][1] = 0;
            Matrix y = matrix_pow(x, n-2, 2);
    
            LL t1 = (y.v[0][0] + y.v[0][1])%(mod-1);
            LL t2 = (y.v[1][0] + y.v[1][1])%(mod-1);
    
            LL ans1 = num_pow(b, t1);
            LL ans2 = num_pow(a, t2);
            LL ans = ans1*ans2%mod;
            printf("%lld\n", ans);
        }
        return 0;
    }
    Matrix multiply(const Matrix &a, const Matrix &b, int Matrix_len){
        Matrix tmp;
        memset(tmp.v, 0, sizeof(tmp.v));
        for(int i = 0; i < Matrix_len; i++){
            for(int j = 0; j < Matrix_len; j++){
                for(int k = 0; k < Matrix_len; k++){
                    tmp.v[i][j] += (a.v[i][k]*b.v[k][j]);
                    tmp.v[i][j] %= (mod-1);
                }
            }
        }
        return tmp;
    }
    Matrix matrix_pow(Matrix &x, int k, int Matrix_len){
        Matrix tmp;
        memset(tmp.v, 0, sizeof(tmp.v));
        for(int i = 0; i < Matrix_len; i++)
            tmp.v[i][i] = 1;
        while(k){
            if(k & 1)
                tmp = multiply(tmp, x, Matrix_len);
            x = multiply(x, x, Matrix_len);
            k >>= 1;
        }
        return tmp;
    }
    LL num_pow(LL num, LL k){
        LL ans = 1;
        while(k){
            if(k & 1)
                ans = ans*num%mod;
            num = num*num%mod;
            k >>= 1;
        }
        return ans;
    }

[vjudge]: https://vjudge.net/problem/HDU-4549