记录编号	78497	评测结果	AAAAAAAAAA
题目名称	eins	最终得分	100
用户昵称	raywzy	是否通过	通过
代码语言	C++	运行时间	4.249 s
提交时间	2013-11-04 07:35:00	内存使用	0.31 MiB

#include<fstream>
using namespace std;
ifstream fin("eins.in");
ofstream fout("eins.out");
class JZ
{
public:
	long long F[4][4];
};
JZ P,K;
int n,p,t;
JZ Mul1(JZ A,JZ B)//2x2的矩阵乘以2x1的矩阵
{
	JZ TEMP;
	TEMP.F[1][1]=(A.F[1][1]*B.F[1][1]+A.F[1][2]*B.F[2][1])%p;
	TEMP.F[2][1]=(A.F[2][1]*B.F[1][1]+A.F[2][2]*B.F[2][1])%p;
	return TEMP;
}
JZ Mul2(JZ A,JZ B)//2x2乘以2x2的矩阵
{
	JZ TEMP;
	TEMP.F[1][1]=(A.F[1][1]*B.F[1][1]+A.F[1][2]*B.F[2][1])%p;
	TEMP.F[2][1]=(A.F[2][1]*B.F[1][1]+A.F[2][2]*B.F[2][1])%p;
	TEMP.F[1][2]=(A.F[1][1]*B.F[1][2]+A.F[1][2]*B.F[2][2])%p;
	TEMP.F[2][2]=(A.F[2][1]*B.F[1][2]+A.F[2][2]*B.F[2][2])%p;
	return TEMP;
}
JZ Ksm(JZ A,int B)
{
	if(B==1) return A;
	int temp;
	JZ flag;
	temp=B>>1;
	flag=Ksm(A,temp);
	flag=Mul2(flag,flag);
	if(B%2==0)
		return flag;
	else
		return Mul2(flag,A);
}
int main()
{
	fin>>t;
	P.F[1][1]=1;P.F[1][2]=1;P.F[2][1]=1;P.F[2][2]=0;
	K.F[1][1]=1;K.F[2][1]=0;
	int i,A,B;
	JZ TEMP;
	for(i=1;i<=t;i++)
	{
		fin>>n>>p;
		if(n==0)
		{
			fout<<0%p<<endl;
			continue;
		}
		if(n==1)
		{
			fout<<1%p<<endl;
			continue;
		}
		TEMP=Ksm(P,n-1);
		TEMP=Mul1(TEMP,K);
		fout<<TEMP.F[1][1]<<endl;
	}
	return 0;
}