上善若水

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  2 Posts :: 32 Stories :: 2 Comments :: 0 Trackbacks

常用链接

留言簿

我参与的团队

最新随笔

搜索

  •  

积分与排名

  • 积分 - 10150
  • 排名 - 1170

最新评论

阅读排行榜

评论排行榜

 

//PKU 3070 ,calculate Fibonacci 
#include <iostream>
#include
<stack>
int FPM(int);//fast-power-modulus function declare
using namespace std;
const int Mod=10000;
int main(int argc, char *argv[])
{
    
int n=0;
    
while(scanf("%d",&n))
    {
        
if(n==-1)
            
break;
        printf(
"%d\n",FPM(n));
    }
    
    
return 0;
}
int FPM(int n)//fast-power-modulus function
{
    
int matr[4]={1,0,0,1};//initialize matrix
    stack<bool>dec;//stack to store binary digit
    while(n)//resolve n to binary digit
    {
        dec.push(
1&n);//get the last binary digit
        n>>=1;
    }
    
while(!dec.empty())
    {
     
//matrix square
        matr[1]=((matr[0]+matr[3])*matr[1])%Mod;
        matr[
0]=(matr[0]*matr[0]+matr[2]*matr[2])%Mod;
        matr[
3]=(matr[3]*matr[3]+matr[2]*matr[2])%Mod;
        matr[
2]=matr[1];
    
//matrix multiply,
        if(dec.top())
        {
            matr[
0]=(matr[0]+matr[1])%Mod;
            matr[
1]=(matr[1]+matr[3])%Mod;
            matr[
3]=matr[2];
            matr[
2]=matr[1];
        }
        dec.pop();
    }
    
return matr[1];//matr[1] is the result F[N]

}

 

posted on 2009-11-21 07:39 上善若水 阅读(60) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理