M斐波那契数列
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
题目类型：费马小定理降幂+矩阵快速幂取模
算法分析：首先要发现a和b的指数值分别按照斐波那契数列的规律递增。最后计算的是a^k1 * b^k2 % p，则等价于求解((a^k1 % p) * (b^k2 % p)) % p。比如求解a^k1 % p的值，此时由于递推之后k1比较大，且模值p是一个素数，则使用费马小定理进行降幂。而且k1的求解需要使用矩阵加速，记住此时模值应该是p - 1！！！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define LL long long const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-6; const double PI = 2 * acos (0.0); const int maxn = 2; long long n = 2;//表示方阵的尺寸，必须恰好为运算的大小 //申请变量 struct Mat { long long mat[maxn][maxn]; }; //重载Mat乘法运算 Mat operator * (Mat a, Mat b) { Mat c; memset (c.mat, 0, sizeof (c.mat)); for (long long k = 0; k < n; k++) { for (long long i = 0; i < n; i++) { if (a.mat[i][k] == 0) continue; for (long long j = 0; j < n; j++) { if (b.mat[k][j] == 0) continue; c.mat[i][j] = (c.mat[i][j] + ((a.mat[i][k] % (MOD - 1)) * (b.mat[k][j] % (MOD - 1)) % (MOD - 1))) % (MOD - 1); } } } return c; } //重载Mat乘幂运算 Mat operator ^ (Mat a, long long k) { Mat c; for (long long i = 0; i < n; i++) for(long long j = 0; j < n; j++) c.mat[i][j] = (i == j); while (k) { if(k & 1) c = c * a; a = a * a; k >>= 1; } return c; } LL mod_f (LL a, LL b, LL p) { LL res = 1, tt = (a % p + p) % p; while (b) { if (b & 1) res = res * tt % p; tt = tt * tt % p; b >>= 1; } return res; } int main() { // CPPFF; LL aa, bb, nn; while (cin >> aa >> bb >> nn) { Mat ma; ma.mat[0][0] = 1, ma.mat[0][1] = 1; ma.mat[1][0] = 1, ma.mat[1][1] = 0; Mat mb; mb.mat[0][0] = 1, mb.mat[1][0] = 1; Mat res; LL ta, tb; if (nn == 0) cout << aa % MOD << endl; else if (nn == 1) cout << bb % MOD << endl; else if (nn == 2) cout << ((aa % MOD) * (bb % MOD)) % MOD << endl; else if (nn >= 3) { res = ma ^ (nn - 3); res = res * mb; ta = res.mat[0][0]; res = ma ^ (nn - 2); res = res * mb; tb = res.mat[0][0]; // cout << ta << " " << tb << endl; ta = ta % (MOD - 1), tb = tb % (MOD - 1); LL res1 = mod_f (aa, ta, MOD), res2 = mod_f (bb, tb, MOD); cout << ((res1 % MOD) * (res2 % MOD)) % MOD << endl; } } return 0; } |
- « 上一篇：hdu4472
- hdu4763：下一篇 »