HDU3117_Fibonacci_Numbers_fib前四位跟后四位

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

View Code

 1 #include <iostream>
 2 #include <cmath>
 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_JUDGE
25     //freopen("in.txt", "r", stdin);
26 #endif
27     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 }