首页 > 代码库 > Fibonacci

Fibonacci

2024-07-10 21:20:07 224人阅读

Interesting Fibonacci

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 672 Accepted Submission(s): 116

Problem Description

In mathematics, the Fibonacci numbers are a sequence of numbers named after Leonardo of Pisa, known as Fibonacci (a contraction of filius Bonaccio, "son of Bonaccio"). Fibonacci‘s 1202 book Liber Abaci introduced the sequence to Western European mathematics, although the sequence had been previously described in Indian mathematics. The first number of the sequence is 0, the second number is 1, and each subsequent number is equal to the sum of the previous two numbers of the sequence itself, yielding the sequence 0, 1, 1, 2, 3, 5, 8, etc. In mathematical terms, it is defined by the following recurrence relation:

That is, after two starting values, each number is the sum of the two preceding numbers. The first Fibonacci numbers (sequence A000045 in OEIS), also denoted as F[n]; F[n] can be calculate exactly by the following two expressions:

A Fibonacci spiral created by drawing arcs connecting the opposite corners of squares in the Fibonacci tiling; this one uses squares of sizes 1, 1, 2, 3, 5, 8, 13, 21, and 34;
So you can see how interesting the Fibonacci number is. Now AekdyCoin denote a function G(n)

Now your task is quite easy, just help AekdyCoin to calculate the value of G (n) mod C

Input

The input consists of T test cases. The number of test cases (T is given in the first line of the input. Each test case begins with a line containing A, B, N, C (10<=A, B<2^64, 2<=N<2^64, 1<=C<=300)

Output

For each test case, print a line containing the test case number( beginning with 1) followed by a integer which is the value of G(N) mod C

Sample Input

117 18446744073709551615 1998 139

Sample Output

Case 1: 120

Author

AekdyCoin

Power of Fibonacci

Time Limit: 5 Seconds Memory Limit: 65536 KB

In mathematics, Fibonacci numbers or Fibonacci series or Fibonacci sequence are the numbers of the following integer sequence:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...

By definition, the first two numbers in the Fibonacci sequence are 1 and 1, and each subsequent number is the sum of the previous two. In mathematical terms, the sequence F_n of Fibonacci numbers is defined by the recurrence relation F_n = F_{n - 1} + F_{n - 2} with seed values F₁ = 1 and F₂ = 1.

And your task is to find ΣF_i^K, the sum of the K-th power of the first N terms in the Fibonacci sequence. Because the answer can be very large, you should output the remainder of the answer divided by 1000000009.

Input

There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:

There are two integers N and K (0 <= N <= 10¹⁸, 1 <= K <= 100000).

Output

For each test case, output the remainder of the answer divided by 1000000009.

Sample Input

510 14 2020 29999 99987654321987654321 98765

Sample Output

14348783295274049690113297124108672406

Hint

The first test case, 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 = 143.

The second test case, 1²⁰ + 1²⁰ + 2²⁰ + 3²⁰ =3487832979, and 3487832979 = 3 * 1000000009 + 487832952, so the output is 487832952.

Author: ZHOU, Yuchen

题目来源：

基准时间限制：

Fib(N)表示斐波那契数列的第N项（F(0) = 0, F(1) = 1），给出N和K，求Fib(N) mod Fib(K)。

Input

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000)第2 - T + 1行：每行2个数N, K(1 <= N <= 10^18, 1 <= K <= 10^3)

Output

共T行：对应Fib(N) mod Fib(K)的结果。

Input 示例

25 513 5

Output 示例

2014年蓝桥杯的第九题是这样描述的：

给定Fibonacci数列F[]，其中，，求表达式

的值。其中

E - 喵喵的遗憾

Time Limit: 20000/10000MS (Java/Others) Memory Limit: 512000/256000KB (Java/Others)

Submit Status

Problem Description

喵喵因为太弱，没有进Final，终身遗憾。她就挂在了这个题目上。

已知：

F₀ = 1 , F₁ = 1 , F₂ = 2 , F_n = F_n-1+F_n-2

求：

F_{F_{F_n}} Mod P

( 也就是 F[ F[ F[n] ] ] % P )

Input

第一行一个整数 T 代表数据组数(T ≤ 20000)。 <del> 喵以人格担保时限肯定够！！！</del>

以下每行两个整数 N , P (0 ≤ N ≤ 10⁹ , 1 ≤ P ≤ 10⁹)

Output

对于每组数据输出一个整数代表答案。

Sample Input

41 22 34 354 31

Sample Output

Hint

F₁ = 1 , F₁ = 1 , F₁ = 1

F₂ = 2 , F₂ = 2 , F₂ = 2

F₄ = 5 , F₅ = 8 , F₈ = 34

3286: Fibonacci矩阵

Time Limit: 15 Sec Memory Limit: 128 MB Submit: 131 Solved: 29 [Submit][Status]

Description

Input

八个用空格隔开的整数n, m, a, b, c, d, e, f，其中n, m, a, b, d, e为正整数，c, f为非负整数。

Output

一个整数，表示Fib[n][m]对2012182013取模的值。

Sample Input

3 4 1 1 0 1 1 0

Sample Output

144

HINT

n,m,a,b,c,d,e,f<=10^1000000

Source

tangjz原创

优美的Fibonacci数列与矩阵

分类：数学问题 2014-05-09 16:11 212人阅读评论(0) 收藏举报

题目：http://codeforces.com/contest/392/problem/C

题意：给定Fibonacci数列F[]，令，求的值。

广义Fibonacci数列找循环节

分类：数学问题 2014-05-12 15:53 221人阅读评论(0) 收藏举报

今天将来学习如何求广义Fibonacci数列的循环节。

问题：给定，满足，求的循

环节长度。

来源：http://acdreamoj.sinaapp.com/ 1075题

题目来源：

基准时间限制：

斐波那契数列Mod 一个数N会得到一个新的数列，根据同余可以得知，这个数列中的数会出现循环。例如：

F (mod 4) = 0 1 1 2 3 1 ...

F (mod 5) = 0 1 1 2 3 0 3 3 1 4 0 4 4 3 2 0 2 2 4 1 ...

后面的数会出现循环，因此Fib Mod 4的循环节长度是6，Fib Mod 5的循环节长度是20。

给出一个数N，求斐波那契数列Mod N的循环节的长度。

Input

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000)第2 - T + 1行：每行1个数N。（1 <= N <= 10^9)

Output

共T行，每行一个数，对应循环节的长度。

Input 示例

Output 示例

题目来源：

基准时间限制：

Fib(N)表示斐波那契数列的第N项（F(0) = 0, F(1) = 1），给出N和K，求Fib(N) mod Fib(K)。

Input

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000)第2 - T + 1行：每行2个数N, K(1 <= N <= 10^18, 1 <= K <= 10^3)

Output

共T行：对应Fib(N) mod Fib(K)的结果。

Input 示例

25 513 5

Output 示例

题目来源：

基准时间限制：

F(0)= 0

F(1)= 1

F(2)= 1

F(10)= 5 * 11

F(30)= 2^3 * 5 * 11 * 31 * 61

Input

输入1个数N（0 <= N <= 1000）。

Output

输出F(n)的分解(注意示例中的输出格式及空格)。

Input 示例

Output 示例

F(100)= 3 * 5^2 * 11 * 41 * 101 * 151 * 401 * 3001 * 570601

基准时间限制：

斐波那契字符串的定义如下：

f(1) = a

f(2) = b

f(n) = f(n-1) + f(n-2)，(n > 2)

所以前6个斐波那契字符串是："a", "b", "ba", "bab", "babba", "babbabab"

现在给出一个编号n，再给出1个字符串s，求f(n)包含多多少个s。

例如：n = 6，s = "ba"，f(6) = "babbabab"，包含了3个"ba"。输出3。由于数量巨大，只要输出Mod 10^9 + 7的结果。

Input

第1行：1个数N(2 <= N <= 10^18)第2行：一个字符串S(S的长度 <= 10^5)

Output

输出数量Mod 10^9 + 7

Input 示例

6ba

Output 示例

1021	Fibonacci Again	Leojay		(17212/35677)48.24%
1250	Hat‘s Fibonacci	戴帽子的		(2278/6923)32.90%
1568	Fibonacci	daringQQ	Happy 2007	(1484/3238)45.83%
1588	Gauss Fibonacci	DYGG	HDU “Valentines Day” Open Programming Contest 2007-02-14	(885/2030)43.60%
1708	Fibonacci String	linle	HDU 2007-Spring Programming Contest	(1122/3263)34.39%
1848	Fibonacci again and again	lcy	ACM Short Term Exam_2007/12/13	(1907/4528)42.12%
2814	Interesting Fibonacci	AekdyCoin	HDU 1st “Old-Vegetable-Birds Cup” Programming Open Contest	(116/672)17.26%
2855	Fibonacci Check-up		2009 Multi-University Training Contest 5 - Host by NUDT	(626/1120)55.89%
3054	Fibonacci		2009 Multi-University Training Contest 15 - Host by BUAA	(83/212)39.15%
3117	Fibonacci Numbers		IPCP 2005 Northern Preliminary for Northeast North-America	(676/1709)39.56%
3306	Another kind of Fibonacci	wyb	HDOJ Monthly Contest – 2010.02.06	(561/1464)38.32%
3509	Buge‘s Fibonacci Number Problem		2010 ACM-ICPC Multi-University Training Contest（8）——Host by ECNU	(179/643)27.84%
4099	Revenge of Fibonacci		2011 Asia Shanghai Regional Contest	(456/1963)23.23%
4786	Fibonacci Tree		2013 Asia Chengdu Regional Contest	(308/1043)29.53%

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > Fibonacci

Fibonacci

Interesting Fibonacci

Input

Output

Sample Input

Sample Output

Hint

E - 喵喵的遗憾

Problem Description

Input

Output

Sample Input

Sample Output

Hint

3286: Fibonacci矩阵

Description

Input

Output

Sample Input

Sample Output

HINT

Source

优美的Fibonacci数列与矩阵

广义Fibonacci数列找循环节

看完仍有疑问？有类似问题直接问程序猿