杭电OJ 1568

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1568

开始用递归的方法做这道题——1亿条数据，超时是显然的，查了论坛的解题报告，原来这个是用斐波那契数列的通项公式解的。维基百科了斐波那契数列，查到了通公式

又从论坛上得知这个得先对数运算再指数运算，从而取得高4位，然后就豁然了——关键的运算是 10^(lg(x)-[lg(x)])。以下代码。

#include <cstdio> #include <cmath> int fib_array[47]; void InitFib() { fib_array[0] = 0; fib_array[1] = 1; for (int i=2; i<47; ++i) { fib_array[i] = fib_array[i-2] + fib_array[i-1]; } for (int i=21; i<47; ++i) { while(fib_array[i] > 10000) { fib_array[i] /= 10; } } } double sq5 = sqrt(5); double lg2 = log10((double)2); double lg5 = log10((double)5); int FibHahaha(int i) { double temp = -0.5*lg5 - i*lg2; double a = temp + i*log10(1 + sq5); int na = (int)a; double aa = pow(10.0, a - na); double b = temp + i*log10(sq5 - 1); int nb = (int)b; double bb = pow(10.0, b - nb); int sub = na - nb; double r = (1-(i&1)<<1)*pow(10.0, -(double)sub)*bb + aa; r *= 10000; if (r >= 10000.0) { r /= 10; } return (int)r; } int main() { InitFib(); int a; while (scanf("%d", &a) != EOF) { if (a < 47) { printf("%d\n", fib_array[a]); } else { printf("%d\n", FibHahaha(a)); } } return 0; }