Problem 1438 --Fibonacci数列(二)

1438: Fibonacci数列(二)

上一题 正确率: $154.25\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $365$ 正确数量 $563$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 二分 矩阵快速幂 数论

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

.

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
1000000000
-1

Sample Output复制

0
34
6875

提示

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:

.

推荐代码 查看1438 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$0 $ms] 姚家宝 851521 2022-05-06 22:37:13
内存最少[$0 $KB] yaoking 615011 2020-10-07 19:19:41
第一AC 范晋豪@信息与计算科学142 16689 2016-10-20 20:00:30
第一挑战 范晋豪@信息与计算科学142 16689 2016-10-20 20:00:30

赛题来源/所属竞赛 NA N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛
1800 2023-2024-2学期<计算机专业竞赛实训> 第4周练习：递推和动态规划【22计算机】 2024-03-18 00:00:00 请登录
1770 2023-2024-1学期<编译原理> 第13-14周练习：LR(k)文法实验【21计算机1234】 2023-11-27 00:00:00 请登录
1755 2022-2023-2学期<计算机专业竞赛实训> 第11周练习： 数论,博弈,矩阵【21计算机12345】 2023-04-28 08:00:00 请登录
1740 2022-2023-2学期<计算机专业竞赛实训> 第6周练习：递推和动态规划【21计算机12345】 2023-03-27 00:00:00 请登录
1690 2021-2022-2学期<算法分析与设计> 第11周练习： 博弈 概率 几何 矩阵 2022-05-02 00:00:00 请登录