题目中有两种情况，分别是n <= 39和n > 39两种情况。

前一种只要打个表满足条件的时候直接输出就可以了。

对于后一种分别求前四位和后四位则需要一些前置知识，分别是对数运算和矩阵快速幂。

对于前一种，贴一张推导公式，原链接：https://www.cnblogs.com/Blogggggg/p/7356668.html

 

这样就能求出前四位，对于后四位，则需要算出第n项斐波那契数列的值，然后取余运算。

 

 于是有以下代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cmath>
 6 using namespace std;
 7 const int MAXN = 2;
 8 typedef long long LL;
 9 LL fib[45];
10 void init(){
11     fib[1] = 1;
12     for(int i = 2; i <= 40; i ++)
13         fib[i] = fib[i - 1] + fib[i - 2];
14 }
15 struct Matrix{
16     LL m[MAXN][MAXN];
17     Matrix(){
18         memset(m, 0, sizeof(m));
19     }
20 };
21 int find_head(int n){
22     double t = -0.5 * log10(5.0) + n * log10((1 + pow(5, 0.5)) / 2);
23     t -= floor(t);
24     double temp = pow(10.0, t + 3);
25     return int(temp);
26 }
27 Matrix multi(Matrix a, Matrix b){
28     Matrix res;
29     memset(res.m, 0, sizeof(res.m));
30     for(int i = 0; i < MAXN; i ++)
31         for(int j = 0; j < MAXN; j ++)
32             for(int k = 0; k < MAXN; k ++)
33                 res.m[i][j] += (a.m[i][k] * b.m[k][j] % 10000);
34     return res;
35 }
36 Matrix last(Matrix a, int n){
37     Matrix res;
38     memset(res.m, 0, sizeof(res.m));
39     for(int i = 0; i < 2; i++)
40         res.m[i][i] = 1;
41     while(n){
42         if(n & 1)
43             res = multi(res, a);
44         a = multi(a, a);
45         n >>= 1;
46     }
47     return res;
48 }
49 int main(){
50     init();
51     LL n;
52     while(cin >> n){
53         if(n <= 39)
54             cout << fib[n] << endl;
55         else{
56             Matrix ori;
57             ori.m[1][1] = ori.m[0][1] = ori.m[1][0] = 1;
58             ori.m[0][0] = 0;
59             printf("%04d....%04d\n",find_head(n), last(ori, n - 1).m[0][0] % 10000);
60         }
61     }
62     return 0;
63 }