程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu4549---M斐波那契數列(矩陣+歐拉定理)

hdu4549---M斐波那契數列(矩陣+歐拉定理)

編輯：C++入門知識

hdu4549---M斐波那契數列(矩陣+歐拉定理)

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

Source
2013金山西山居創意游戲程序挑戰賽——初賽（2）

Recommend
liuyiding | We have carefully selected several similar problems for you: 5189 5188 5186 5185 5184

可以發現,每一項上面的指數,剛好是fib數
但是直接做指數太大,mod為素數
所以根據歐拉定理
mod的歐拉函數值為mod-1
a^b = a^(b%(mod - 1)
然後就可以做了

/*************************************************************************
    > File Name: hdu4549.cpp
    > Author: ALex
    > Mail: [email protected] 
    > Created Time: 2015年03月16日 星期一 20時12分13秒
 ************************************************************************/

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair  PLL;

const LL mod = 1000000006;

class MARTIX
{
    public:
        LL mat[3][3]; 
        MARTIX();
        MARTIX operator * (const MARTIX &b)const;
        MARTIX& operator = (const MARTIX &b);
};

MARTIX :: MARTIX()
{
    memset (mat, 0, sizeof(mat));
}

MARTIX MARTIX :: operator * (const MARTIX &b)const
{
    MARTIX ret;
    for (int i = 0; i < 2; ++i)
    {
        for (int j = 0; j < 2; ++j)
        {
            for (int k = 0; k < 2; ++k)
            {
                ret.mat[i][j] += this -> mat[i][k] * b.mat[k][j];
                ret.mat[i][j] %= mod;
            }
        }
    }
    return ret;
}

MARTIX& MARTIX :: operator = (const MARTIX &b)
{
    for (int i = 0; i < 2; ++i)
    {
        for (int j = 0; j < 2; ++j)
        {
            this -> mat[i][j] = b.mat[i][j];
        }
    }
    return *this;
}

MARTIX fastpow(MARTIX A, int n)
{
    MARTIX ans;
    ans.mat[0][0] = ans.mat[1][1] = 1;
    while (n)
    {
        if (n & 1)
        {
            ans = ans * A;
        }
        n >>= 1;
        A = A * A;
    }
    return ans;
}

LL fast(LL a, LL n)
{
    LL b = 1;
    while (n)
    {
        if (n & 1)
        {
            b = a * b % 1000000007;
        }
        a = a * a % 1000000007;
        n >>= 1;
    }
    return b;
}

int main ()
{
    LL a, b, n;
    while (~scanf("%lld%lld%lld", &a, &b, &n))
    {
        MARTIX F;
        F.mat[0][0] = F.mat[0][1] = F.mat[1][0] = 1;
        if (n == 0)
        {
            printf("%lld\n", a);
            continue;
        }
        if (n == 1)
        {
            printf("%lld\n", b);
            continue;
        }
        MARTIX A;
        A.mat[0][0] = 1;
        A.mat[0][1] = 0;
        F = fastpow(F, n - 1);
        F = A * F;
        LL cnt1 = F.mat[0][1];
        LL cnt2 = F.mat[0][0];
        LL ans = fast(a, cnt1);
        ans = ans * fast(b, cnt2) % 1000000007;
        printf("%lld\n", ans);
    }
    return 0;
}