HDU4549 M斐波那契数列（矩阵快速幂+费马小定理）

February 25, 2016

题目链接

斐波那契数列的矩阵表示：

欧拉函数：对正整数 n，是小于或等于 n 的正整数中与 n 互质的数的数目。又称为 φ 函数。

欧拉定理（也称费马-欧拉定理或欧拉函数定理）是一个关于同余的性质。欧拉定理表明，若为正整数，且互素（即），则

即

与 1 在模 n 下同余；φ(n)为欧拉函数。

如果 A，C 互质，那么 A^B %C=A^( B%phi(C) ) %C

f(0) = a, f(1) = b;

f(n) = f(n-1)*f(n-2);

最后化为 f(n) = ((a^x)*(b^y)) %mod;

而 x 与 y 是斐波那契数，而且 mod 是素数；

所以根据公式：a^b%c == a^(b %phi(c))%c;

c 是素数 φ(c)=c-1 所以直接化为：

a^b%c == a^(b %(c-1))%c

因此 f(n)=a^(Fib[n-1]%(m-1))*b^(Fib[n]%(m-1))%m

#include<cstring>
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const double pi = acos(-1);
const int MOD = 1000000007;
 
struct Matrix{
    long long mat[2][2];
};
const Matrix I ={
    1, 0,
    0, 1,
};
const Matrix P ={
    1, 1,
    1, 0,
};
Matrix matrixmul(Matrix a,Matrix b){
    Matrix ret;
    for(int i = 0; i < 2; i++)
        for(int j=0;j<2;j++){
            ret.mat[i][j] = 0;
            for(int k = 0; k < 2; k++){
                ret.mat[i][j] += (a.mat[i][k]*b.mat[k][j])%(MOD-1);
                ret.mat[i][j] %= (MOD-1);
            }
        }
    return ret;
}
 
Matrix M_quickpow(long long n){
    Matrix m = P, ret = I;
    while (n){
        if (n & 1) ret = matrixmul(ret, m);
        n >>= 1;
        m = matrixmul(m, m);
    }
    return ret;
}
 
long long quickmod(long long a, long long n, long long MOD){
    long long r = 1;
    while(n){
        if(n&1){
            r = (a*r)%MOD;
        }
        a = (a*a)%MOD;
        n >>= 1;
    }
    return r;
}
 
int main(){
    //freopen("a.txt", "r", stdin);
    int a, b, n;
    Matrix q;
    while (~scanf("%d%d%d", &a, &b, &n)){
        q = M_quickpow(n);
        long long ans = quickmod(a, q.mat[1][1], MOD) * quickmod(b, q.mat[1][0], MOD) % MOD;
        printf("%lldn", ans);// (a^Fib(n-1)*b^Fib(n)) %M
    }
    return 0;
}