hdu1568斐波那契前4位

题意：

就是求斐波那契数，但是只要求输出前四位，（n<=100000000）。

思路：

这个要用到斐波那契的公式和一些log的规律，直接打看着很乱，直接在网上偷张图片吧：

然后就是一些log的性质

log10(a^b) = b * log10(a),log10(a*b) = log10(a) + log10(b)

我们可以根据这个把大数的前几位拿出来，这样：

log10(1234567890)

= log10(1.234567890 * 10^9)

= log10(1.234567890) + 9

这样我们就得到了一个"小数部分"bit = log10(1.234567890)

然后pow(10.0 ,bit) = 1.234567890

这样我们就得到了一个大数的科学技术法的前边部分，想要四位，直接*1000取整就行了。

#include<stdio.h>

#include<math.h>



int num[25];

void ini()

{

   num[0] = 0 ,num[1] = 1;

   for(int i = 2 ;i <= 20 ;i ++)

   num[i] = num[i-1] + num[i-2];

}

int main ()

{

    ini();

    int n;

    while(~scanf("%d" ,&n))

    {

       if(n <= 20)

       {

          printf("%d\n" ,num[n]);

          continue;

       }

       double now = -0.5 * log10 (5.0) + n * 1.0 * log10((1+sqrt(5.0))/2.0);

       double bit = now - (int)now;

       double a = pow(10.0,bit);

       a *= 1000;

       printf("%d\n" ,int(a));

    }

    return 0;

}

巴特西

hdu1568斐波那契前4位

最新文章

热门文章