Problem Description
M斐波那契數(shù)列F[n]是一種整數(shù)數(shù)列，它的定義如下：
F[0] = a
F[1] = b
F[n] = F[n-1] * F[n-2] ( n >1 )
現(xiàn)在給出a, b, n，你能求出F[n]的值嗎？
Input
輸入包含多組測(cè)試數(shù)據(jù)；
每組數(shù)據(jù)占一行，包含3個(gè)整數(shù)a, b, n（ 0<= a, b, n<= 10^9 ）
Output
對(duì)每組測(cè)試數(shù)據(jù)請(qǐng)輸出一個(gè)整數(shù)F[n]，由于F[n]可能很大，你只需輸出F[n]對(duì)1000000007取模后的值即可，每組數(shù)據(jù)輸出一行，
hdu4549M斐波那契數(shù)列(矩陣+歐拉定理)
。Sample Input
0 1 0 6 10 2
Sample Output
0 60
Source
2013金山西山居創(chuàng)意游戲程序挑戰(zhàn)賽——初賽（2）
Recommend
liuyiding | We have carefully selected several similar problems for you: 5189 5188 5186 5185 5184
可以發(fā)現(xiàn),每一項(xiàng)上面的指數(shù),剛好是fib數(shù)
但是直接做指數(shù)太大,mod為素?cái)?shù)
所以根據(jù)歐拉定理
mod的歐拉函數(shù)值為mod-1
a^b = a^(b%(mod - 1)
然后就可以做了
<code class=" hljs cpp">/************************************************************************* >File Name: hdu4549.cpp >Author: ALex >Mail: zchao1995@gmail.com >Created Time: 2015年03月16日 星期一 20時(shí)12分13秒 ************************************************************************/#include<map>#include<set>#include<queue>#include<stack>#include<vector>#include<cmath>#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#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<int, int>PLL;const LL mod = 1000000006;class MARTIX{ public: LL mat[3][3]; MARTIX(); MARTIX operator * (const MARTIX &b)const; MARTIX& perator = (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 :: perator = (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;}</code>