记录编号	125837	评测结果	AAAAAAAAAA
题目名称	eins	最终得分	100
用户昵称	Dijkstra	是否通过	通过
代码语言	C++	运行时间	3.104 s
提交时间	2014-10-10 11:21:22	内存使用	0.31 MiB

#include<fstream>
using namespace std;
ifstream fin("eins.in");
ofstream fout("eins.out");
int p,a,t;
struct square
{
	long long x1,x2,y1,y2;
};
square operator *(square a,square b)
{
	square ans;
	ans.x1=a.x1*b.x1+a.x2*b.y1;ans.x1%=p;
	ans.x2=a.x1*b.x2+a.x2*b.y2;ans.x2%=p;
	ans.y1=a.y1*b.x1+a.y2*b.y1;ans.y1%=p;
	ans.y2=a.y1*b.x2+a.y2*b.y2;ans.y2%=p;
	return ans;
}
square MOD(square x,int y)
{
	if(y<=1) return x;
	if(y%2==0) return MOD(x*x,y/2);
	return MOD(x*x,y/2)*x;
}
int main()
{
	fin>>t;
	square b={1,0,0,0},f={1,1,1,0};
	for(int i=1;i<=t;i++)
	{
		fin>>a>>p;
		if(a==0)
		{
			fout<<"0"<<endl;
			continue;
		}
	    fout<<((b*MOD(f,a-1)).x1)%p<<endl;
	}
	return 0;
}