注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

Fibonacci  

2010-05-20 22:23:00|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Description

In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn ? 1 + Fn ? 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

An alternative formula for the Fibonacci sequence is

Fibonacci - 东月之神 - 东月之神.

Given an integer n, your goal is to compute the last 4 digits of Fn.

Input

The input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 ≤ n ≤ 1,000,000,000). The end-of-file is denoted by a single line containing the number ?1.

Output

For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000).

Sample Input

0 9 999999999 1000000000 -1

Sample Output

0 34 626 6875

Hint

As a reminder, matrix multiplication is associative, and the product of two 2 × 2 matrices is given by

Fibonacci - 东月之神 - 东月之神.

Also, note that raising any 2 × 2 matrix to the 0th power gives the identity matrix:

Fibonacci - 东月之神 - 东月之神.

强大的矩阵乘法。。

#include <cstdio>  

int a[5], b[5], c[5], v[5], n;
 
int main()  
{  
    while(scanf("%d", &n) != EOF && n != -1)  
    {  
          a[1] = 1; a[2] = 1; a[3] = 1; a[4] = 0;  
          b[1] = 1; b[2] = 0; b[3] = 0; b[4] = 1;  
          if(n == 0)  {printf("0\n"); continue;}  
          while(n)  
          {  
                if(n & 1)    
                {  
                      c[1] = (a[1] * b[1] + a[2] * b[3]) % 10000;  
                      c[2] = (a[1] * b[2] + a[2] * b[4]) % 10000;  
                      c[3] = (a[3] * b[1] + a[4] * b[3]) % 10000;  
                      c[4] = (a[3] * b[2] + a[4] * b[4]) % 10000;  
                      b[1] = c[1]; b[2] = c[2]; b[3] = c[3]; b[4] = c[4];  
                }  
                v[1] = (a[1] * a[1] + a[2] * a[3]) % 10000;  
                v[2] = (a[1] * a[2] + a[2] * a[4]) % 10000;  
                v[3] = (a[3] * a[1] + a[4] * a[3]) % 10000;  
                v[4] = (a[3] * a[2] + a[4] * a[4]) % 10000;  
                a[1] = v[1]; a[2] = v[2]; a[3] = v[3]; a[4] = v[4];  
                n >>= 1;  
          }
    printf("%d\n", c[2]);
    }  
return 0;  

  评论这张
 
阅读(147)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017