10的1000次方，谁有想法请进！！

Fibonacci 数列有如下特点：其第 1 ， 2 项均为 1 ， 1 。从第 3 个数开始，该数是其前两个数之和 . 即 :


F1=1 (n=1)
F2=1 (n=2)
Fn=Fn-1+Fn-2 (n>=3)
请你编写一个函数 fun ，它的功能是：对于一个给定的 数（ N ）， 求不大于 N 的最大 Fibonacci 数。

输入

输入的第一行是一个正整数，表示下面有几组数据需要计算。之后的每一行是一个数据 N ，其中 1 < N <= 10的1000次方。

输出

对应输入的每一行，输出一个 不大于 N 的最大 Fibonacci 数。

简单的问题，复杂的算法，好像要字符串，可又不会用字符进行加减运算，望进来的高手指点一下算法，只要算法不要程序。
----------------解决方案--------------------------------------------------------
这种题有难度..我写的方法只是能算出结果..还没考虑效率..昨天就有这样的题目已经发了程序了..就在c的论坛里面
----------------解决方案--------------------------------------------------------
#include "stdio.h"
int main(void)
{
   int temp[1000];
   int i;
   temp[0]=1;
   for(i=1;i<1000;i++)
      temp[i]=0;
   for(i=0;i<1000;i++)
      printf("%d",temp[i]);      
   return 0;      
}
----------------解决方案--------------------------------------------------------
要是5的1000次方怎么办啊？（投机）
----------------解决方案--------------------------------------------------------
先答完 10
----------------解决方案--------------------------------------------------------
有快速算fib的算法
fib(n)=fx-1*fy+fx*fy+1
x+y=n
同时用二分可以增加速度
----------------解决方案--------------------------------------------------------
高精度乘法直接用数组模拟
----------------解决方案--------------------------------------------------------
复杂度是(logN)^4吧
先简单估个上下界就快了
----------------解决方案--------------------------------------------------------
只有有难度的问题``才能勾出高手们啊``
----------------解决方案--------------------------------------------------------
是啊..大家都隐藏起来了...
----------------解决方案--------------------------------------------------------