记录编号	74949	评测结果	AAAAAAAAAA
题目名称	1426.eins	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	5.118 s
提交时间	2013-10-26 19:27:32	内存使用	0.31 MiB

#include<fstream>
using namespace std;
ifstream fi("eins.in");
ofstream fo("eins.out");
typedef unsigned long long ull;
const int matrix_size=3;
int t;
ull N,M;
ull quick_multi(ull x,ull y)//快速乘
{
	if(y==0)return 0;
	if(y==1)return x%M;
	ull temp=quick_multi(x,y/2);
	temp=(temp<<1)%M;
	if(y%2==1)temp+=x;
	return temp%M;
}
class matrix
{
public:
	int n,m;//n行m列
	ull p[matrix_size][matrix_size];//下标从1开始
	matrix(){n=m=0;}
};
matrix operator *(matrix &a,matrix &b)
{
	matrix ans;
	ans.n=a.n;ans.m=b.m;
	for(int i=1;i<=ans.n;i++)
		for(int j=1;j<=ans.m;j++)
		{
			ans.p[i][j]=0;
			for(int k=1;k<=a.m;k++)
			{
				ans.p[i][j]+=(a.p[i][k]*b.p[k][j])%M;
			}
			ans.p[i][j]%=M;
		}
	return ans;
}
matrix matrix_quick(matrix a,ull n)//矩阵快速幂
{
	if(n==1)return a;
	matrix temp=matrix_quick(a,n/2);
	temp=temp*temp;
	if(n%2==1)temp=temp*a;
	return temp;
}
int main()
{
	fi>>t;
	matrix example,ans,temp,T;
	example.n=example.m=2;
	example.p[1][1]=1;example.p[2][1]=1;
	example.p[1][2]=1;example.p[2][2]=0;
	ans.n=1;ans.m=2;
	ans.p[1][1]=0;
	ans.p[1][2]=1;
	for(int i=1;i<=t;i++)
	{
		fi>>N>>M;
		if(N==0){fo<<0<<endl;continue;}
		temp=matrix_quick(example,N);
		T=ans*temp;
		fo<<T.p[1][1]<<endl;
	}
	return 0;
}