## Fibonacci Sequence

View as PDF

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

The Fibonacci sequence is a well known sequence of numbers in which

Given a number , find the Fibonacci number, modulo .
Note: For 30% of the marks of this problem, it is guaranteed that .

#### Input Specification

The first line of input will have the number .

#### Output Specification

The Fibonacci number, modulo .

#### Sample Input

26

#### Sample Output

121393

• crackersamdjam  commented on May 15, 2018, 8:09 p.m.

Tim, it's not there. The code works fine on my machine

• crackersamdjam  commented on May 14, 2018, 10:38 p.m.

Hey Dmoj, Does anyone know what RTE(aborted) means? Thanks

• rsylshzxdkh  commented on Aug. 22, 2017, 2:29 p.m. edited

Help

Java TLE

Never mind I got it

• sunnylancoder  commented on March 20, 2017, 11:02 p.m.

They said it couldn't be done - 0.02 seconds AC

oh yeah mr krabbs I beet quantum!

• sunnylancoder  commented on Dec. 5, 2016, 11:05 p.m.

Requires basic math knowledge, but I mainly solved it by observation/logic.

• r3mark  commented on Dec. 5, 2016, 11:15 p.m.

The intended solution uses matrices which is considered advanced math for DMOJ tags.

• aCookieBreak  commented on June 15, 2016, 8:33 p.m.
Timothy, are you submitting my altered code?

@global_smurf

• Kirito  commented on June 15, 2016, 8:40 p.m.

r3mark hijacked global smurf cuz he submiited some 15+ pointers on it.

• r3mark  commented on Nov. 28, 2015, 11:41 a.m. edit 2
Time machine

This submission was submitted in December 2015. https://dmoj.ca/submission/25109 https://gyazo.com/384dbe04e5e09316b99739e7eb9497ca

Edit: Fixed, timestamp now says 2014.

• DanAlexanderIlicio  commented on Aug. 6, 2015, 12:20 a.m.
No idea

I have no idea how to do the Sequence. In my algorithm first, module Output (d=n% 1 000 000 0007) , after sending the result to the method:

static int mo=1000000007;
static int fib(int d){
int x = 0, y = 1, z = 1;
for (long i = 0; i < d; i++) {
x = y%mo;
y = z;
z = x + y;
z=z%mo;
}
return x;
}

But still very it slow when passing a very large number as d= 333 333 716 .

• kobortor  commented on Aug. 8, 2015, 8:35 p.m.
• Tan  commented on May 27, 2015, 8:06 p.m. edited
Program Question

NVM

• BMP  commented on May 27, 2015, 9:58 p.m.

This is not a recursive problem.

• arock  commented on May 27, 2015, 8:19 p.m.
• FatalEagle  commented on Sept. 15, 2014, 9:16 p.m.
Modular Arithmetic

The problem requires you to output mod . That means that you need to get the remainder of the final answer when it is divided by . This operation can be done in Python, C++, and Java by using '%'.

Example:
999999999999999999999999 mod 1000000007
is 999999999999999999999999 % 1000000007
which is equal to 48999999.
Because 999999999999999999999999  = 999999993000000 * 1000000007 + 48999999,
48999999 is 999999999999999999999999 (mod 1000000007).

It may interest you to know that is a prime number.

There are a two highly useful properties of modular arithmetic we often use in programming competitions (% has the same precedence as multiplication and division):

• quantum  commented on Sept. 13, 2014, 4:30 p.m. edited
Difficulty

This problem is a lot more difficult than it may appear. There is a reason for 15 points. The input can be as big as .