Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • Calculate Fibonacci n-th term modulo m

    Fibonacci sequence is defined by obtaining each next term in the sequence by adding up the previous two, while the first two elements are 0 and 1:
    Given the number n, you are asked to calculate the n-th Fibonacci numbers modulo m.
    As we’re only interested in the result modulo m, the value of n can be very large.

    Input

    The only line of the input contains two integers n (0 ≤ n ≤ ) and m (1 ≤ m ≤ 50).

    Output

    The program should print the result of .

    Examples

    Input
    Output
    0 5
    0
    1 5
    1
    6 5
    3

    Explanation

    1. fib(0) = 0 ⇒ 0 mod 5 = 0
    1. fib(1) = 1 ⇒ 1 mod 5 = 1
    1. fib(6) = 8 ⇒ 8 mod 5 = 3
     
    Hint 1
    As we’re calculating the fibonacci numbers modulo m, and the next number always depends on the previous two, the numbers start to repeat at some point. You can try printing many values modulo m and notice the pattern after which they start repeating.
    Hint 2
    As the numbers start repeating at some point, you can directly calculate the n-th Fibonacci number instead of looping through all of them.

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue