13369 - Fibonacci Sequence   

Status  |  Limits Submit

Description

In this problem, you are asked to help us develop a method to compute the n-th term, Fn, of the fibonacci sequence. The fibonacci sequence is a recursive sequence defined as Fi=Fi-1+Fi-2, where we let F0=0, F1=1 in this problem. This recursive relation can be written as a matrix multiplication:

and this is the general form of Fn and Fn+1:

This problem is a partial judge problem. You are asked to design a function to calculate (Ab % m) where A is a 2x2 matrix and b,m are integers. Then, using your function and the matrix equation above, we are able to compute our desired Fn of the fibonacci sequence. For the details, please check the main() function carefully.

 

The power computation for integers ...

Given integers a, b and m, calculating the answer of (ab % m) may be trivial for you because it can be solved by using a single for loop:

for (int i = 0; i < b; i++) ans = ans * a % m;

, or a recursive way:

int pow(int a, int b) {
    if (b == 0) return 1;
    return a * pow(a, b-1);
}

However, this isn't the best way to do so since its time complexity is O(b). In other words, it requires b times of steps, so it may not be able to finish the task in a second if b is large (e.g. b <= 1018).

Therefore, we have another better algorithm to achieve it. Define a function P(a,b)=ab. For P(a,b), we don't need the answer of P(a, b-1). Instead, we are interested in the answer of P(a, b/2). To explain why, we discuss in two cases of P(a,b):

  1. b is even: ab = ab/2 * ab/2
  2. b is odd: ab = ab/2 * ab/2 * a

The code below is a demonstration of this simple algorithm.

int pow1(int a, int b) {
    if (b==0) return 1;
    int t = pow1(a, b/2);
    if (b%2 == 0) t = t * t % m;
    else          t = t * t % m * a % m;
    return t;
}

Next, we want to analyze the time complexity, or, the steps required to solve this problem. Since pow(a,b) will only call the function pow(a,b/2) once, there're log2(b) of steps. Therefore, the time complexity is O(log(b)), which is much more efficient than the original method O(b).

Note that the following implementation can give the right answer, but the time complexity is still O(b). It is recommended to figure the reason out with your thoughts.

int pow2(int a, int b) {
    if (b==0) return 1;
    if (b%2 == 0) return pow2(a, b/2) * pow2(a, b/2) % m;
    else          return pow2(a, b/2) * pow2(a, b/2) % m * a % m;
}

 

In this problem ...

In this problem, for us to compute Fn of the fibonacci sequence, you are asked to design a function to calculate (Ab % m) where A is a 2x2 matrix and b,m are integers.

This function has the following prototype, as declared in function.h:

long long* matrix_pow(long long *A, long long b, long long m) {
    
}

 

  • Note 1: The 2x2 matrix A is represented as a 1-D long long int array of length 4, which is in the following format:

.

  • Note 2: Please malloc a 1-D long long int array of length 4 in matrix_pow() to store the computed (Ab % m), and return the address of this malloced dynamic array as the function's return value.
  • Note 3:

A0=, the 2x2 identity matrix.

  • Note 4: You can consider to define/implement other function(s) in your function.c to help complete the design of your matrix_pow(), if you feel necessary.

Input

The input only consists of two integers n and m, where 0 <= n <= 1018, 0 < m <=2*109.

Output

Output Fn % m in a single line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13369.c

Partial Judge Header

13369.h

Tags




Discuss