文件详细信息

下载本文件

本文件的大小为 2035 字节。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<ext/pb_ds/assoc_container.hpp>
template<typename T>
void read(T&num){
	int ch=getchar();
	num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
template<typename T>
void write(T a){
	static int ch[20],cnt=0;
	if(a<0)putchar('-'),a=-a;
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|48,a/=10;
	while(cnt)putchar(ch[--cnt]);
}
typedef unsigned int uint;
typedef unsigned long long ull;
const uint size=2;
uint T,p,a,b,x1,t,m;
ull qpow(ull a,uint x){
	ull ans=1;
	while(x){
		if(x&1)ans=ans*a%p;
		a=a*a%p;
		x>>=1;
	}
	return ans;
}
struct Matrix{
	ull v[size][size];
	Matrix(){
		memset(v,0,sizeof(v));
	}
}I,A,B,trans,cur,step;
Matrix operator*(const Matrix a,const Matrix b){
	Matrix ans;
	for(uint i=0;i<size;i++)
		for(uint j=0;j<size;j++)
			for(uint k=0;k<size;k++)
				ans.v[i][j]=(ans.v[i][j]+a.v[i][k]*b.v[k][j])%p;
	return ans;
}
Matrix qpow(Matrix a,uint x){
	Matrix ans=I;
	while(x){
		if(x&1)ans=ans*a;
		a=a*a;
		x>>=1;
	}
	return ans;
}
bool operator==(const Matrix a,const Matrix b){
	for(uint i=0;i<size;i++)
		for(uint j=0;j<size;j++)
			if(a.v[i][j]!=b.v[i][j])
				return false;
	return true;
}
struct custom_hash{
	uint operator()(const Matrix a)const{
		uint hash=0;
		for(uint i=0;i<size;i++)
			for(uint j=0;j<size;j++)
				hash=hash*p+a.v[i][j];
		return hash;
	}
};
__gnu_pbds::gp_hash_table<Matrix,uint,custom_hash>map;
int solve(){
	read(p),read(a),read(b),read(x1),read(t);
	if(x1==t)return 1;
	if(a==0)return b==t?2:-1;
	m=sqrt(p)+1;
	map.clear();
	A.v[0][0]=x1,A.v[0][1]=1;
	B.v[0][0]=t,B.v[0][1]=1;
	trans.v[0][0]=a,trans.v[0][1]=0;
	trans.v[1][0]=b,trans.v[1][1]=1;
	cur=B;
	for(uint i=0;i<=m;i++){
		map[cur]=i;
		cur=cur*trans;
	}
	step=qpow(trans,m),cur=A*step;
	for(uint i=1;i<=m;i++){
		if(map.find(cur)!=map.end())return i*m-map[cur]+1;
		cur=cur*step;
	}
	return-1;
}
int main(){
	for(uint i=0;i<size;i++)I.v[i][i]=1;
	read(T);
	while(T--)write(solve()),putchar('\n');
	return 0;
}