题目

Constraints

Time Limit: 1 secs, Memory Limit: 32 MB 

Description

Fibonacci numbers are nice simple integers. All of you are familiar with it, aren’t you?
The Fibonacci sequence <F[n]> are defined by the recurrence:
F[0]=0;
F[1]=1;
F[n]=F[n-1]+F[n-2], for n>1
You know that the value of F[n] increases rapidly when the n becomes larger. So for each test case,output the value F[n] mod m will be ok. 

Input

The first line of the input is a positive integer.It is the number of the test cases followed. Each test case contains two integers n (0<=n<2^32) and m (0<m<10000). There may be one or several spaces between the two integers. 

Output

The output of the program should consist of one line of output for each test case.The output of each test case only contains one integer which equals to the value F[n] mod m. No any redundant spaces are needed. 

Sample Input

2
1 1000
2 100

Sample Output
1
1

思路

使用矩阵乘法来快速求出对应的斐波那契数列项。

代码

// Copyright (c) 2014 Junjie_Huang@SYSU(SNO:13331087). All Rights Reserved.
// 1863.c: http://soj.me/1863
#include<stdio.h>
#include<string.h>

void matrix_copy(long long matrix_2[2][2], long long matrix_tmp[2][2]) {
  int i, j;
  for (i = 0; i < 2; i++) {
    for (j = 0; j < 2; j++) {
      matrix_2[i][j] = matrix_tmp[i][j];
    }
  }
}

void matrix_multiplication(long long matrix_1[2][2],
                           long long matrix_2[2][2],
                           long long m) {
  long long matrix_tmp[2][2] = { 0 };
  matrix_tmp[0][0] = (matrix_1[0][0] * matrix_2[0][0]
                      + matrix_1[0][1] * matrix_2[1][0]) % m;
  matrix_tmp[1][0] = (matrix_1[1][0] * matrix_2[0][0]
                      + matrix_1[1][1] * matrix_2[1][0]) % m;
  matrix_tmp[0][1] = (matrix_1[0][0] * matrix_2[0][1]
                      + matrix_1[0][1] * matrix_2[1][1]) % m;
  matrix_tmp[1][1] = (matrix_1[1][0] * matrix_2[0][1]
                      + matrix_1[1][1] * matrix_2[1][1]) % m;
  matrix_copy(matrix_2, matrix_tmp);
}

void matrix_pow(long long matrix[2][2],
                long long matrix_tmp[2][2],
                long long n, long long m) {
  if (n == 0) {
    matrix_tmp[0][0] = 0;
    return;
  } else if (n == 1) {
    return;
  }

  n -= 2;
  while (n) {
    if (n & 1) matrix_multiplication(matrix, matrix_tmp, m);
    matrix_multiplication(matrix, matrix, m);
    n >>= 1;
  }
  return;
}

int main() {
  int T;
  long long n, m;
  long long matrix_0[2][2] = { { 1, 1 }, { 1, 0 } },
    matrix_result[2][2] = { { 1, 1 }, { 1, 0 } },
    matrix_tmp[2][2] = { { 1, 1 }, { 1, 0 } };

  scanf("%d", &T);
  while (T--) {
    matrix_copy(matrix_tmp, matrix_0);
    matrix_copy(matrix_result, matrix_0);
    scanf("%lld %lld", &n, &m);
    matrix_pow(matrix_tmp, matrix_result, n, m);
    printf("%d\n", matrix_result[0][0]);
  }

  return 0;
}