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

M斐波那契数列

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)

Problem Description

M斐波那契数列F[n]是一种整数数列，它的定义如下：

F[0] = a
F[1] = b
F[n] = F[n-1] * F[n-2] ( n > 1 )

现在给出a, b, n，你能求出F[n]的值吗？

Input

输入包含多组测试数据；
每组数据占一行，包含3个整数a, b, n（ 0 <= a, b, n <= 10^9 ）

Output

对每组测试数据请输出一个整数F[n]，由于F[n]可能很大，你只需输出F[n]对1000000007取模后的值即可，每组数据输出一行。

Sample Input

0 1 0
6 10 2

Sample Output

0
60

分析：用普通方法提交了一次，果断超时。

写出F(2)、F(3)、F(4)、F(5)…会发现a和b的指数是fib数，如果求出fib数列，用快速幂就可以快速求出最后答案。问题转化为了如何快速求解fib数列。

因为【F(n-2)，F(n-1)】*【0,1,1,1】 = 【F(n-1),F(n)】，所以可以用矩阵乘法来求。

每次相乘的矩阵为

0 1

1 1

为了防止求F(n)时溢出，要对矩阵元素取模，即 a[i][j] %= 1000000006。模数之所以为1000000006是因为根据费马小定理可得A^euler(M) = 1 （mod M）,其中M为素数。

所以A^N = A^（N % euler(M)）（mod M），而1000000007为素数，euler（1000000007）= 1000000006，所以模数是1000000006。

求出F(n-1)和F(n)以后，用二分快速幂求出pow（a，F(n-1)）* pow（b，F(n)）% 1000000007 就是最后的答案。

#include<stdio.h>
#define mod 1000000007
typedef __int64 LL;
struct Matrix
{
    LL mat[2][2];
};

Matrix unit_matrix =
{
    1, 0,
    0, 1
}; //单位矩阵

Matrix mul(Matrix a, Matrix b) //矩阵相乘
{
    Matrix res;
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
        {
            res.mat[i][j] = 0;
            for(int k = 0; k < 2; k++)
            {
                res.mat[i][j] += a.mat[i][k] * b.mat[k][j];
                res.mat[i][j] %= 1000000006;
            }
        }
    return res;
}

Matrix pow_matrix(Matrix a, LL n)  //矩阵快速幂
{
    Matrix res = unit_matrix;
    while(n != 0)
    {
        if(n & 1)
            res = mul(res, a);
        a = mul(a, a);
        n >>= 1;
    }
    return res;
}

LL pow(LL a, LL n) //二分快速幂
{
    a %= mod;
    LL res = 1;
    while(n != 0)
    {
        if(n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main()
{
    LL a, b, n;
    Matrix tmp;
    tmp.mat[0][0] = 0;
    tmp.mat[0][1] = tmp.mat[1][0] = tmp.mat[1][1] = 1;
    while(~scanf("%I64d%I64d%I64d",&a,&b,&n))
    {
        Matrix p = pow_matrix(tmp, n); //p.mat[0][0]即为F(n-1)，p.mat[1][0]即为F(n)
        LL ans = (pow(a, p.mat[0][0]) * pow(b, p.mat[1][0])) % mod;
        printf("%I64d\n",ans);
    }
    return 0;
}

hdu 4549 M斐波那契数列（费马小定律 + 二分快速幂 + 矩阵快速幂）

M斐波那契数列

相关推荐