hdu 4549 M斐波那契数列 【矩阵+快速幂+欧拉定理】

M斐波那契数列

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1746 Accepted Submission(s): 503

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）

构建矩阵：
base.m[0][0] = 0; base.m[0][1] = 1;
base.m[1][0] = 1; base.m[1][1] = 1;

由欧拉定理：
A^B %C 题中C是质素，而且A，C是互质的。
所以C的欧拉函数值为C-1;
所以由欧拉定理，直接A^(B%(C-1)) %C

比较一般的结论是 A^B %C=A^( B%phi(C)+phi(C) ) %C B>=phi(C)

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <ctype.h>
#include <time.h>
#include <queue>

using namespace std;

const long long MOD = 1000000007;

struct node
{
    long long m[2][2];
}ans, base;
int  a, b, n;

node multi(node a, node b)
{
    node tmp;
    for (int i = 0; i<2; i++)
        for (int j = 0; j<2; j++)
        {
            tmp.m[i][j] = 0;
            for (int k = 0; k<2; k++)
            {
                tmp.m[i][j] = (tmp.m[i][j] + a.m[i][k] * b.m[k][j]) % (MOD-1);//由欧拉定理
            }
        }
    return tmp;
}

void fast_mod(int n)// 求矩阵 base 的  n 次幂
{
    base.m[0][0] = 0; base.m[0][1] = 1;
    base.m[1][0] = 1; base.m[1][1] = 1;

    ans.m[0][0] = ans.m[1][1] = 1;// ans 初始化为单位矩阵
    ans.m[0][1] = ans.m[1][0] = 0;
    while (n)
    {
        if (n & 1) //实现 ans *= t; 其中要先把 ans赋值给 tmp，然后用 ans = tmp * t
            ans = multi(ans, base);
        base = multi(base, base);
        n >>= 1;
    }
}

long long quickpow(long long m, long long n, long long k)//快速幂
{
    long long  b = 1;
    long long mm =m%k;
    while (n > 0)
    {
        if (n & 1)
            b = (b*mm) % k;
        n = n >> 1;
        mm = (mm*mm) % k;
    }
    return b;
}
//////////////////////
int main()
{
    while (scanf("%d %d %d", &a, &b, &n) == 3)
    {
        if (n == 0)
        {
            printf("%d\n", a%MOD );
            continue;
        }
        if (n == 1)
        {
            printf("%d\n", b%MOD );
            continue;
        }
        fast_mod(n-1);

        //printf("%lld %ld\n\n",ans.m[1][0],ans.m[1][1]);

        int anss = quickpow(a, ans.m[1][0] , MOD)  *  quickpow(b, ans.m[1][1], MOD) % MOD;
        printf("%d\n", anss);
    }
    return 0;
}