怎么求Fibonacci数第n位的位数?编程ACM高精度低精度的就不要了；ProblemdescriptionFibonacci数{0,1,1,2,3,5,8,13,21,34,55,...}的定义如下:F0=0F1=1Fi=Fi-1+Fi-2当i≥2当i相当大时,Fi也很大.现在不要求你求

Question

怎么求 Fibonacci 数第n位的位数?编程ACM 高精度
低精度的就不要了；
Problem description
Fibonacci数{0,1,1,2,3,5,8,13,21,34,55,...}的定义如下:
F0= 0
F1= 1
Fi= Fi-1+ Fi-2当i ≥ 2
当i相当大时,Fi也很大.现在不要求你求出Fi的值,只需要求出Fi的(十进制)位数.
Input
输入有多个正整数,每个整数一行,表示Fibonacci数的序号i（0 < i≤2^20）.
最后是一个0,表示输入结束且不需处理.
Output
对于输入的每个i,输出Fi的位数.
Sample Input
1
100
0
Sample Output
1
21
注意 i 的取值挺大的!
下面我的代码：采用取对通项对数,但是wrong answer
求正确代码!
#include
#include
using namespace std;
int main()
{
double i,m,n,ans;
while(cin>>i&&i)
{
m=(1+sqrt(5))/2;
n=(1-sqrt(5))/2;
ans=log10( ( pow(m,i)-pow(n,i) )/sqrt(5) );
cout

Answer 1

矩阵快速幂.这里矩阵算法不是乘法了 是求10的对数 然后相加.