# HZAU 1202 GCD （矩阵快速幂 + GCD）

## Problem Description

Xiao Ming found the compute time of $\gcd (fib_n,fib_{n+1})$ is the most when he learnt the gcd, and the result of it is always $fib_1$ but he is not satisfied with the simple compute result.

He wants to know what $\gcd (1+S_n,1+S_m)$ equals.

And gcd is greatest common divisor,

$fib_1 = 1, fib_2 = 1, fib_n = fib_{n-1} + fib_{n-2} (n ≥ 3)$

$$S_n=\sum_{i=1}^nfib_i$$

## Input Description

The first line is an positive integer T. (1 ≤ T ≤ 10^3) indicates the number of test cases. In the next T lines, there are three positive integer n, m, p(1 ≤ n, m, p ≤ 10^9) at each line.

## Output Description

In each test case, output the compute result of $\gcd (1+S_n,1+S_m)\%p$ at one line.

## Sample Input:

1
1 2 3


## Sample Output:

1


## 思路

$\gcd (F_n,F_m)=F_{\gcd (n,m)}$

$F_1+F_2+F_3+F_4+F_5+…+F_n+1=F_{n+2}$

## AC 代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
typedef long long LL;

LL n,m,mod;
LL gcd(LL a,LL b)
{
if(b==0)return a;
return gcd(b,a%b);
}

struct node
{
LL mp[2][2];
void init(LL a,LL b,LL c,LL d)
{
mp[0][0]=a;
mp[0][1]=b;
mp[1][0]=c;
mp[1][1]=d;
}
void mult(node x,node y)                //两矩阵乘法
{
memset(mp,0,sizeof(mp));
for(LL i=0; i<2; i++)
for(LL j=0; j<2; j++)
for(LL k=0; k<2; k++)
mp[i][j]=(mp[i][j]+x.mp[i][k]*y.mp[k][j])%mod;
};
} init;

struct node expo(struct node x, LL k)  //进行k次幂运算
{
struct node tmp;
tmp.init(1,0,0,1);                      //单位矩阵
while(k)                                //快速幂部分
{
if(k&1)tmp.mult(tmp,x);
x.mult(x,x);
k>>=1;
}
return tmp;
}

int main()
{
int T;
ios::sync_with_stdio(false);
cin>>T;
while(T--)
{
cin>>n>>m>>mod;
int k=gcd(n+2,m+2);
init.init(1,1,1,0);
cout<<expo(init,k).mp[0][1]%mod<<endl;
}
return 0;
}