记录编号	77569	评测结果	AAAAAAAAAA
题目名称	eins	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	2.627 s
提交时间	2013-11-02 09:06:20	内存使用	0.31 MiB

#include <fstream>
using namespace std;
ifstream fi("eins.in");
ofstream fo("eins.out");
long long n,t,p;
void ksm(long long &a,long long &b,long long &c,long long &d,long long m)
{
	long long aa,bb,cc,dd;
	if (m==1||m==0) return;
	if (m%2==0)
	{
		ksm(a,b,c,d,m/2);
		aa=a;bb=b;cc=c;dd=d;
		a=aa*aa+bb*cc;a%=p;
		b=aa*bb+bb*dd;b%=p;
		c=aa*cc+cc*dd;c%=p;
		d=bb*cc+dd*dd;d%=p;
		return;
	}else
	{
		ksm(a,b,c,d,m/2);
		aa=a;bb=b;cc=c;dd=d;
		a=aa*aa+bb*cc;a%=p;
		b=aa*bb+bb*dd;b%=p;
		c=aa*cc+cc*dd;c%=p;
		d=bb*cc+dd*dd;d%=p;
		aa=a;bb=b;cc=c;dd=d;
		a=aa+bb;a%=p;
		b=aa;b%=p;
		c=cc+dd;c%=p;
		d=cc;d%=p;
		return;
	}
}
int main()
{
	long long i,a,b,c,d;
	fi>>t;
	for (i=1;i<=t;i++)
	{
		fi>>n>>p;
		if (n==0) {fo<<0<<endl;continue;}
		a=1;b=1;c=1;d=0;
		ksm(a,b,c,d,n-1);
		fo<<a%p<<endl;
	}
	return 0;
}