菲波那契数的余数------大数

Description

菲波那契数大家可能都已经很熟悉了： f(1)=0 f(2)=1 f(n)=f(n-1)+f(n-2) n>2 因此，当需要其除以某个数的余数时，不妨加一些处理就可以得到。

Input

输入数据为一些整数对P、K，P(1 < P < 5000)表示菲波那契数的序号，K( 1 <= K < 15)表示2的幂次方。遇到两个空格隔开的0时表示结束处理。

Output

输出其第P个菲波那契数除以2的K次方的余数。

Sample Input

6 2
20 10
0 0

Sample Output

1
85

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<algorithm>
 5 #include<cstring>
 6 using namespace std;
 7 int dp[5005][2001];
 8 
 9 int main()
10 {
11     int mi[16],sum,len;
12     mi[0]=1;
13     for(int i=1;i<16;i++)
14     mi[i]=mi[i-1]*2;
15     memset(dp,0,sizeof(dp));
16     dp[1][2000]=0;
17     dp[2][2000]=1;len=1;
18     for(int i=3;i<5001;i++)
19     {
20         sum=0;
21         for(int k=2000;k>2000-len;k--)
22         {
23             sum=dp[i-1][k]+dp[i-2][k]+sum;
24             dp[i][k]=sum%10;
25             sum=sum/10;
26             if(k==2000-len+1&&sum>0)
27             {
28                 dp[i][2000-len]=sum;
29                 len++;
30                 break;
31             }
32         }
33     }
34 
35     int k,p,t;
36     while(cin>>p>>k&&(p&&k))
37     {
38         for(t=0;t<=2000;t++)
39         if(dp[p][t]!=0)
40         break;
41         sum=0;
42         for(int i=t;i<=2000;i++)
43         sum=(sum*10+dp[p][i])%mi[k];
44         cout<<sum<<endl;
45     }
46     return 0;
47 }

View Code

一个大数问题，分开算的。不知道如何打表，打表用时太长了