/**State: 3117    0MS    424K    1028 B    C++*题目大意：*        求出第nth个fib数，要求大于8位的只输出前4位跟后4位。*解题思路：*        后四位可以用矩阵快速幂来求，但是根据模的特性，发现原来*        周期15000fib又会回来。所以可以用数组来保存这个循环节即可。*        而前四位可以用log10.来计算，原来就是每一个数都可以用科学*        计数法来表示，我们用log10来取出每一个数科学计数法的那几个*        决定位权数的值，然后要n位就乘以10^n.不过要注意精度问题哦。*/

1 #include 
      
        2 #include 
       
         3 using namespace std; 4  5 const int MAX = 16000; 6 int mod = 10000; 7 int fiblast[MAX] = {
    0, 1, 1}, fib[MAX] = {
    0, 1, 1}; 8 double N1 = (1.0 + sqrt(5.0)) / 2.0; 9 10 void pre_init()11 {12     for(int i = 3; i < MAX; i++)13     {14         fiblast[i] = (fiblast[i - 1] + fiblast[i - 2]) % mod;15         if(fiblast[i] == fiblast[1] && fiblast[i - 1] == fiblast[0])16             break;17         fib[i] = fib[i - 1] + fib[i - 2];18     }19     return ;20 }21 22 int main(void)23 {24 #ifndef ONLINE_JUDGE25     //freopen("in.txt", "r", stdin);26 #endif27     pre_init();28     int n;29     while(scanf("%d", &n) == 1)30     {31         if(n < 40)32         {33             printf("%d\n", fib[n]);34             continue;35         }36         double k = log10(1.0/sqrt(5.0)) + (double)n * log10(N1);37         //((1-sqrt(5)) / 2)^n当n==40的时候已经小数点后10位了，38         //可以忽略，本题不要求那么高的精度39         double tmp = k;40         tmp = k - (int)tmp;41         printf("%d...%0.4d\n", (int)(1000.0 * pow(10.0, tmp)), fiblast[n % 15000]);42     }43     return 0;44 }