M斐波那契数列

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

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

题解：

1.可知f[n]中a、b的指数符合斐波那契数列，因而可用矩阵快速幂求出。

2.然而如果指数不求模，也可能会溢出。但指数又怎样求模呢？

有如下定理：当m为素数，且a、n互质时， a^n % m = a^(n%(m-1)) % m。

证明：

根据费马小定理，当m为素数，且a、p互质时， a^(m-1) ≡ 1 (mod m)，

a^n = a^(k*(m-1)+r) = (a^(m-1))^k * a^r，其中 r = n%(m-1)，

那么 a^n % m = ( (a^(m-1))^k * a^r ) % m = (a^(m-1))^k % m * a^r % m = 1 * a^r % m = a^(n%(m-1)) % m 。

所以：当m为素数，且a、n互质时， a^n % m = a^(n%(m-1)) % m 。

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <cmath>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const int INF = 2e9;
15 const LL LNF = 9e18;
16 const int MOD = 1000000007;
17 const int MAXN = 1e6+100;
18 
19 const int Size = 2;
20 struct MA
21 {
22     LL mat[Size][Size];
23     void init()
24     {
25         for(int i = 0; i<Size; i++)
26         for(int j = 0; j<Size; j++)
27             mat[i][j] = (i==j);
28     }
29 };
30 
31 MA mul(MA x, MA y)
32 {
33     MA ret;
34     memset(ret.mat, 0, sizeof(ret.mat));
35     for(int i = 0; i<Size; i++)
36     for(int j = 0; j<Size; j++)
37     for(int k = 0; k<Size; k++)
38         ret.mat[i][j] += (1LL*x.mat[i][k]*y.mat[k][j])%(MOD-1), ret.mat[i][j] %= (MOD-1);
39     return ret;
40 }
41 
42 MA qpow(MA x, LL y)
43 {
44     MA s;
45     s.init();
46     while(y)
47     {
48         if(y&1) s = mul(s, x);
49         x = mul(x, x);
50         y >>= 1;
51     }
52     return s;
53 }
54 
55 LL q_pow(LL x, LL y)
56 {
57     LL s = 1;
58     while(y)
59     {
60         if(y&1) s *= x, s %= MOD;
61         x *= x, x %= MOD;
62         y >>= 1;
63     }
64     return s;
65 }
66 
67 MA tmp = {
68     1, 1,
69     1, 0
70 };
71 
72 int main()
73 {
74     LL f[2], n;
75     while(scanf("%lld%lld%lld",&f[0],&f[1],&n)!=EOF)
76     {
77         if(n<=1)
78         {
79             printf("%lld
", f[n]%MOD);
80             continue;
81         }
82 
83         MA s = tmp;
84         s = qpow(s, n-1);
85         LL p1 = s.mat[0][0];
86         LL p2 = s.mat[1][0];
87         LL ans = q_pow(f[0], p2)*q_pow(f[1], p1)%MOD;
88         printf("%lld
", ans);
89     }
90 }

View Code