Hdu3117 Fibonacci numbers [mathematics]

Topic link ：

​ ​http://acm.hdu.edu.cn/showproblem.php?pid=3117​​

The main idea of the topic ：

Give you an integer N(0 <= N <= 10^8), Find Fibonacci number number number number number number N term F[N] The first four digits and the last four digits of .

Ideas ：

Fibonacci sequence is a big number , Direct violence enumeration is obviously unscientific . Consider the end first 4 Whether the bit has a cyclic section , Write a

The program found that the loop section is 15000, Directly use the array to store the front 15000 At the end of the Fibonacci sequence of 4 position . As for Fibonacci

Before the sequence 4 position . It is calculated that N >= 40 after ,F[N] Greater than 8 Number of digits . about N < 40 The part of can be directly

Output results , about N >= 40 Part of , Consider the formula F[N] =(1/√5) * ( ((1+√5)/2)^n - ((1-√5)/2)^n ).

set up F[N] Can be expressed as t * 10^k(t Is a decimal ), So right. F[N] = t * 10^k Take logarithms on both sides log10, obtain ：

log10(F[N]) = log10(t) + k .log10(t) = log10(F[N]) - k, because t It must be less than 10 Decimals of , therefore ,

log10(t) < 1, and k Integers , that log10(t) The value is log10(F[N]) Remove the decimal part of the integer part .

use pow(10.0,log10(t)) Find out t. take t*1000 Take the integer part and you get F[N] Before 4 position .

And a little bit more , seek F[N] = (1/√5) * ( ((1+√5)/2)^n - ((1-√5)/2)^n ) When , because N>=40 When ,

((1-√5)/2)^n It is already a very small decimal ( After the decimal point 10 Bit left and right ), So you can directly ignore . It looks like ,

F[N] ≈ (1/√5) * ((1+√5)/2)^n.log10(F[N]) Simplify ：1/sqrt(5.0) + N*log10(1+(sqrt(5.0))/2.0).

AC Code ：

Log in and copy

      
      

       
       #include<iostream>
       
       

       
       #include<algorithm>
       
       

       
       #include<cstdio>
       
       

       
       #include<cstring>
       
       

       
       #include<cmath>
       
       

       
       using 
       
       namespace 
       
       std;
       
       

       
       

       
       int 
       
       f[
       
       15010],
       
       f1[
       
       110];
       
       

       
       

       
       int 
       
       main()
       
       
{
       
       
    
       
       f[
       
       0] 
       
       = 
       
       0,
       
       f[
       
       1] 
       
       = 
       
       1;
       
       
    
       
       for(
       
       int 
       
       i 
       
       = 
       
       2; 
       
       i 
       
       <= 
       
       15001; 
       
       i
       
       ++) 
       
       // Save the last four digits 
       
       
        
       
       f[
       
       i] 
       
       = (
       
       f[
       
       i
       
       -
       
       1] 
       
       + 
       
       f[
       
       i
       
       -
       
       2])
       
       %
       
       10000;
       
       

       
       
    
       
       f1[
       
       0] 
       
       = 
       
       0,
       
       f1[
       
       1] 
       
       = 
       
       1;
       
       
    
       
       for(
       
       int 
       
       i 
       
       = 
       
       2; 
       
       i 
       
       <= 
       
       100; 
       
       ++
       
       i)     
       
       //0~39
       
       
    {
       
       
        
       
       f1[
       
       i] 
       
       = (
       
       f1[
       
       i
       
       -
       
       1] 
       
       + 
       
       f1[
       
       i
       
       -
       
       2]);
       
       
        
       
       if(
       
       f1[
       
       i] 
       
       >= 
       
       100000000)
       
       
        {
       
       
            
       
       break;
       
       
        }
       
       
    }
       
       

       
       
    
       
       int 
       
       N;
       
       
    
       
       while(
       
       cin 
       
       >> 
       
       N)
       
       
    {
       
       
        
       
       if(
       
       N 
       
       <= 
       
       39)
       
       
            
       
       cout 
       
       << 
       
       f1[
       
       N] 
       
       << 
       
       endl;
       
       
        
       
       else
       
       
        {
       
       
            
       
       double 
       
       temp 
       
       = 
       
       log10(
       
       1
       
       /
       
       sqrt(
       
       5.0)) 
       
       + 
       
       N
       
       *
       
       log10((
       
       1
       
       +
       
       sqrt(
       
       5.0))
       
       /
       
       2.0);
       
       
            
       
       temp 
       
       -= (
       
       int)
       
       temp;
       
       
            
       
       temp 
       
       = 
       
       pow(
       
       10.0,
       
       temp);
       
       
            
       
       while(
       
       temp 
       
       < 
       
       1000)
       
       
                
       
       temp 
       
       *= 
       
       10;
       
       
            
       
       int 
       
       ans 
       
       = (
       
       int)
       
       temp;
       
       
            
       
       printf(
       
       "%d...",
       
       ans);
       
       
            
       
       printf(
       
       "%4.4d\n",
       
       f[
       
       N
       
       %
       
       15000]);
       
       
        }
       
       
    }
       
       

       
       

       
       
    
       
       return 
       
       0;
       
       
}
      
      
      
      

       
       
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.