记录编号	77709	评测结果	AAAAAAAAAA
题目名称	1426.eins	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	5.235 s
提交时间	2013-11-02 14:13:09	内存使用	0.31 MiB

#include<fstream>
using namespace std;
ifstream fi("eins.in");
ofstream fo("eins.out");
int p;
class mat
{
	public:
			int x,y;
			long long ma[3][3];
};
mat operator *(mat &a,mat &b)
{
	mat t;
	int i,j,k;
	t.x=a.x;
	t.y=b.y;
	for(i=1;i<=a.x;i++)
	{
		for(j=1;j<=b.y;j++)
		{
			t.ma[i][j]=0;
			for(k=1;k<=a.y;k++)
			{
				t.ma[i][j]=(t.ma[i][j]+(a.ma[i][k]*b.ma[k][j]))%p;
			}
			t.ma[i][j]%=p;
		}
	}
	return t;
}
mat pow(mat x,int n)
{
	if(n==1)return x;
	mat t=pow(x,n/2);
	if(n%2==0)return t*t;
	if(n%2==1)
	{
		t=t*t;
		return t*x;
	}
}
int main()
{
	int n,t,i;
	mat ans,T,O;
	fi>>n;
	T.x=2;T.y=2;
	T.ma[1][1]=1;
	T.ma[1][2]=1;
	T.ma[2][1]=1;
	T.ma[2][2]=0;
	O.x=1;O.y=2;
	O.ma[1][1]=1;
	O.ma[1][2]=0;
	for(i=1;i<=n;i++)
	{
		fi>>t>>p;
		if(t==0)
		{
			fo<<"0"<<endl;
			continue;
		}
		ans=pow(T,t);
		ans=O*ans;
		fo<<ans.ma[1][2]<<endl;
	}
	return 0;
}