记录编号	208393	评测结果	AAAAAAAAAA
题目名称	[CodeChef FN] 斐波那契数	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	8.014 s
提交时间	2015-11-16 15:43:08	内存使用	62.00 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
typedef long long LL;
//取模,返回非负数 
LL realmod(LL a,LL M){
	a%=M;
	if(a<0) a+=M;
	return a;
}
//快速幂,用普通乘法实现 
LL quickpow(LL a,LL n,LL M){
	a=realmod(a,M);
	LL ans=1;
	while(n){
		if(n&1) ans=ans*a%M;
		a=a*a%M;
		n>>=1;
	}
	return ans;
}
//乘法逆元 
LL inverse(LL a,LL p){//a对p的乘法逆元,p是素数 
	return quickpow(a,p-2,p);
}
//勒让德符号 
LL Legendre_symbol(LL a,LL p){//p是奇素数 
	//1代表a是平方剩余,-1代表a不是平方剩余,0代表a=0 
	//a^((p-1)/2)
	LL flg=quickpow(a,(p-1)/2,p);
	if(flg==0||flg==1) return flg;
	if(flg==p-1) return -1;
}
//模意义平方根 
LL sqrt_mod(LL n,LL p){//解方程组x^2=n(mod p),Tonelli-Shanks算法,p是奇素数
	n=realmod(n,p);//保证n非负 
	//返回方程的一个根 
	if(Legendre_symbol(n,p)!=1) return -1;//无解
	LL S=0,Q=p-1; 
	while(!(Q&1)){
		S++;
		Q>>=1;
	}
	//现在Q是奇数,p-1=Q*2^S
	LL z;//选择一个二次非剩余z 
	while(true){
		z=rand()%p;//随机一个数,这个rand有可能太小,不知道会不会出问题 
		if(Legendre_symbol(z,p)==-1) break;
	}
	LL c=quickpow(z,Q,p),R=quickpow(n,(Q+1)/2,p),t=quickpow(n,Q,p),M=S,i,tmp,b;
	while(true){
		if(t==1) return R;
		for(i=0,tmp=t;tmp!=1;i++,tmp=tmp*tmp%p);
		b=quickpow(c,1LL<<(M-i-1),p),R=R*b%p,c=b*b%p,t=t*c%p,M=i;
	}
}
//二次同余方程 
bool quadratic_mod(LL a,LL b,LL c,LL p,LL &x1,LL &x2){//解同余方程ax^2+bx+c=0(mod p),p是奇素数 
	a=realmod(a,p),b=realmod(b,p),c=realmod(c,p);
	LL dlt=realmod(b*b%p-4*a%p*c%p,p);
	LL sd=sqrt_mod(dlt,p);
	if(sd==-1) return false;//无解
	LL inv2a=inverse(2*a,p);
	x1=realmod((-b+sd)%p*inv2a,p);
	x2=realmod((-b-sd)%p*inv2a,p);
	return true;
}
//扩展欧几里得算法 
void extend_gcd(LL a,LL b,LL &x,LL &y,LL &d){
	if(b==0){d=a;x=1;y=0;}
	else{extend_gcd(b,a%b,y,x,d);y-=(a/b)*x;}
}
vector<pair<LL,LL> > suspects;
LL C,P,ans;
void update(LL n){
	if(ans==-1||n<ans) ans=n;
}
const int HSIZE=3233983;
class Node{
public:
	int s;
	LL a;
	int nxt;
};
class Hash_Map{
public:
	int head[HSIZE];
	Node lis[HSIZE];
	int tot;
	void clear(void){
		memset(head,0,sizeof(head));
		tot=0;
	}
	bool count(int s){
		int key=s%HSIZE;
		for(int x=head[key];x;x=lis[x].nxt){
			if(lis[x].s==s) return true;
		}
		return false;
	}
	LL& operator [] (int s){
		int key=s%HSIZE,x;
		for(x=head[key];x;x=lis[x].nxt){
			if(lis[x].s==s) return lis[x].a;
		}
		lis[++tot]=(Node){s,-1,head[key]};
		head[key]=tot;
		return lis[tot].a;
	}
};
Hash_Map base;
//求离散对数,大步小步算法 
void dclog(LL a,LL MOD){//求解方程:a^x=b(mod MOD),返回最小解,无解返回-1
	//采用大步小步法
	a=realmod(a,MOD);
	base.clear();
	LL m=(LL)sqrt(MOD+0.5),e=1,i,v;
	v=inverse(quickpow(a,m,MOD),MOD);
	base[1]=0;
	for(i=1;i<m;i++){
		e=(e*a)%MOD;
		if(!base.count(e)) base[e]=i;
	}
	for(i=0;i<=MOD/m;i++){
		for(LL j=0;j<suspects.size();j++){
			LL &b=suspects[j].first;
			if(base.count(b)){
				update((i*m+base[b])*2+suspects[j].second);
			}
			b=(b*v)%MOD;
		}
	}
}
void test_even(LL y,LL u){//y^n=u(mod P),n为偶数 
	LL v=sqrt_mod(u,P),m;
	if(v==-1) return;
	suspects.push_back(make_pair(realmod(v,P),0));
	suspects.push_back(make_pair(realmod(-v,P),0));
}
void test_odd(LL y,LL u){//y^n=u(mod P),u为奇数 
	LL v=sqrt_mod(u*inverse(y,P),P),m;
	if(v==-1) return;
	suspects.push_back(make_pair(realmod(v,P),1));
	suspects.push_back(make_pair(realmod(-v,P),1));
}
void work(void){
	LL x=sqrt_mod(5,P);//根号5 
	LL y=realmod((x+1)*inverse(2,P),P);
	ans=-1;
	suspects.clear();
	LL d=C*x%P,u1,u2;
	//y^n-(-1/y)%n=d
	//情况1:n是偶数 
	if(quadratic_mod(1,-d,-1,P,u1,u2)){
		test_even(y,u1);
		test_even(y,u2);
	}
	//情况2:n是奇数
	if(quadratic_mod(1,-d,+1,P,u1,u2)){
		test_odd(y,u1);
		test_odd(y,u2);
	}
	dclog(y,P);
	printf("%lld\n",ans);
}
int main(void){
	freopen("fn.in","r",stdin);
	freopen("fn.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%lld%lld",&C,&P);
		work();
	}
	return 0;
}