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) ) %CB>=phi(C)
namespace std;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 * tans = multi(ans, base);base = multi(base, base);n >>= 1;}}m, 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;}
我想去旅行，一个人背包，一个人旅行，
