hdu 4549 M斐波那契数列 (矩阵快速幂+费马小定理+指数循环节)
题意：M斐波那契数列F[n]是一种整数数列，它的定义如下：
F[0] = a F[1] = b F[n] = F[n-1] * F[n-2] ( n > 1 )
现在给出a, b, n，你能求出F[n]的值吗？
思路：观察发现。。。F[n] = a^(fib(n-1)) * b ^ (fib(n))
此处要用到指数循环节的知识：
a^n ≡ a^(n % Phi(M) + Phi(M)) (mod M) (n >= Phi(M))
然后 因为1000000007是质数，对于任意的x,有gcd(x,1000000007) = 1，所以可以结合费马小定理化简上式：
a^n ≡ a^(n%(m-1)) * a^(m-1)≡ a^(n%(m-1)) (mod m)
记得特判一下n为0和1的情况。
xiaodingli
1/* ***********************************************
2Author :111qqz
3Created Time :Wed 26 Oct 2016 09:16:22 AM CST
4File Name :code/hdu/4549.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const LL mod = 1E9+7;
32LL a,b,n;
33struct Mat
34{
35 LL mat[2][2];
36 void clear()
37 {
38 ms(mat,0);
39 }
40}M,M1;
41Mat operator * ( Mat a,Mat b)
42{
43 Mat res;
44 res.clear();
45 for ( int i = 0 ; i < 2 ; i ++)
46 for ( int j = 0 ; j < 2 ; j++)
47 for ( int k = 0 ; k < 2 ; k++)
48 res.mat[i][j] = (res.mat[i][j] + a.mat[i][k] * b.mat[k][j] ) % (mod - 1);
49 return res;
50}
51Mat operator ^ (Mat a,LL b)
52{
53 Mat res;
54 res.clear();
55 for ( int i = 0 ; i < 2 ; i++) res.mat[i][i] = 1;
56 while (b>0)
57 {
58 if (b&1) res = res * a;
59 b = b >> 1LL;
60 a = a * a ;
61 }
62 return res;
63}
64LL ksm( LL a,LL b)
65{
66 LL res = 1LL;
67 while (b>0)
68 {
69 if (b&1){
70 res = (res * a) %mod;
71 }
72 b = b >> 1LL;
73 a = ( a * a ) % mod;
74 }
75 return res;
76}
77void init()
78{
79 M.clear();
80 M.mat[0][1] = 1;
81 M.mat[1][0] = 1;
82 M.mat[1][1] = 1;
83 M1.clear();
84 M1.mat[0][0] = 0;
85 M1.mat[1][0] = 1;
86}
87int main()
88{
89 #ifndef ONLINE_JUDGE
90 freopen("code/in.txt","r",stdin);
91 #endif
92 while (~scanf("%lld %lld %lld",&a,&b,&n))
93 {
94 if (n==0)
95 {
96 printf("%lld\n",a);
97 continue;
98 }
99 if (n==1)
100 {
101 printf("%lld\n",b);
102 continue;
103 }
104 init();
105 Mat ans;
106 ans.clear();
107 ans = (M ^(n-1))*M1;
108 LL x = ans.mat[0][0];
109 LL y = ans.mat[1][0];
110 LL ret =(ksm(a,x)*ksm(b,y))%mod;
111 printf("%lld\n",ret);
112 }
113 #ifndef ONLINE_JUDGE
114 fclose(stdin);
115 #endif
116 return 0;
117}