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

February 25, 2016

题目链接

中文题。

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


begin{pmatrix} F_{n+2} & F_{n+1} \ F_{n+1} & F_{n} end{pmatrix}
=
begin{pmatrix} 1 & 1 \ 1 & 0 end{pmatrix}^{n + 1}

欧拉函数:对正整数 n,varphi(n)是小于或等于 n 的正整数中与 n 互质的数的数目。又称为 φ 函数。

欧拉定理(也称费马-欧拉定理欧拉{varphi}函数定理)是一个关于同余的性质。欧拉定理表明,若n,a为正整数,且n,a互素(即gcd(a,n)=1),则

a^{varphi(n)} equiv 1 pmod n

a^{varphi(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;
}

Profile picture

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]