博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
NYOJ148fibonacci数列(二)
阅读量:6439 次
发布时间:2019-06-23

本文共 1217 字,大约阅读时间需要 4 分钟。

fibonacci数列(二)

时间限制:
1000 ms  |  内存限制:
65535 KB
难度:
3
 
描述

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

.

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

 

Hint

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

.

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

.

 

 
输入
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.
输出
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).
样例输入
091000000000-1
样例输出
0346875
View Code
1   2 #include
3 #define N 20000 4 int f[N]={
0,1}; 5 int findT() 6 { 7 int i,j,k; 8 for(i=2;i

 

转载于:https://www.cnblogs.com/zhaojiedi1992/archive/2012/11/14/zhaojiedi1992_2012_11_02.html

你可能感兴趣的文章
linux命令--nslookup
查看>>
.net 时间戳互相转换(精确到毫秒)
查看>>
彻底弄懂css中单位px和em,rem的区别
查看>>
项目管理Redmine和版本跟踪SVN的完美结合
查看>>
MVC5:使用Ajax和HTML5实现文件上传功能
查看>>
Unreal Engine 4 C++ 能够创建角色Zoom摄像头(资源)
查看>>
自己动手写一个编译器Tiny语言解析器实现
查看>>
局部标准差实现对比度增强
查看>>
Guide: Solr performance tuning--转载
查看>>
asp.net(c#) Color颜色的转换
查看>>
android十六进制颜色代码转换为int类型数值
查看>>
[saiku] saiku-添加数据源以及保证数据源的一致性
查看>>
SQL Server讲义
查看>>
linux查看和修改系统时间
查看>>
GPUImage简单滤镜使用(二)
查看>>
jQuery each用法及each解析json
查看>>
基于Solr的HBase多条件查询测试
查看>>
IntelliJ IDEA 进行js Debug调试
查看>>
人脸识别经典算法一:特征脸方法(Eigenface)
查看>>
Prism 订阅事件 IEventAggregator 说明
查看>>