题意：F[0] = a，F[1] = b，F[n] = F[n-1] * F[n-2] ( n > 1 )，现在给出a, b, n，你能求出F[n]的值吗？
题解：矩阵快速幂+费马小定理 我们可以用矩阵表示a和b指数的转移，即转移矩阵为 T = [ 1 1 1 0 ] T= \left[ \begin{matrix} 1 & 1 \\ 1 & 0 \\ \end{matrix} \right] T=[1110] 初始矩阵为 m a = [ 0 ( F i − 1 中 a 的 指 数 ) 1 ( F i − 1 中 b 的 指 数 ) 1 ( F i − 2 中 a 的 指 数 ) 0 ( F i − 2 中 b 的 指 数 ) ] ma= \left[ \begin{matrix} 0(F_{i-1}中a的指数) & 1(F_{i-1}中b的指数) \\ 1(F_{i-2}中a的指数) & 0(F_{i-2}中b的指数) \\ \end{matrix} \right] ma=[0(Fi−1中a的指数)1(Fi−2中a的指数)1(Fi−1中b的指数)0(Fi−2中b的指数)] 根据费马小定理：C为质数且A,C互质，A^B % C = A^(B % (C-1)) % C，所以指数的取模是整体取模的模值-1。
最后用快速幂求一下答案即可。
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<queue> #include<stack> #include<cmath> #include<vector> #include<fstream> #include<set> #include<map> #include<sstream> #include<iomanip> #define ll long long using namespace std; //矩阵快速幂 const int mod = 1e9 + 7; struct matrix { ll mat[2][2]; matrix() { memset(mat, 0, sizeof(mat)); } matrix operator * (const matrix& b)const { matrix ans; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { ans.mat[i][j] = 0; for (int k = 0; k < 2; k++) { ans.mat[i][j] = (ans.mat[i][j] + mat[i][k] * b.mat[k][j] % (mod-1) + mod-1) % (mod-1); } } } return ans; } }; matrix q_pow(matrix a, ll b) { matrix ans; memset(ans.mat, 0, sizeof(ans.mat)); for (int i = 0; i < 2; i++) ans.mat[i][i] = 1; while (b) { if (b & 1) ans = ans * a; b >>= 1; a = a * a; } return ans; } //快速幂 ll fastpow(ll base, ll n, ll mod) { ll ans = 1; while (n) { if (n & 1) ans *= base % mod, ans %= mod; base *= base, base %= mod; n >>= 1; } return ans % mod; } int a, b, n; int main() { while (~scanf("%d%d%d", &a, &b, &n)) { if (n == 0) printf("%d\n", a); else if (n == 1) printf("%d\n", b); else { matrix ma; ma.mat[0][0] = ma.mat[0][1] = ma.mat[1][0] = 1; ma.mat[1][1] = 0; ma = q_pow(ma, n - 1); int anum = ma.mat[0][1]; int bnum = ma.mat[0][0]; printf("%d\n", fastpow(a, anum, mod) * fastpow(b, bnum, mod) % mod); } } return 0; }