hdu4549---M斐波那契数列(矩阵+欧拉定理) - c++编程基础

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: zchao1995@gmail.com 
    > 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; }