记录编号	240543	评测结果	AAAAAAAAAA
题目名称	多-有丝分裂	最终得分	100
用户昵称	asddddd	是否通过	通过
代码语言	C++	运行时间	0.314 s
提交时间	2016-03-23 08:30:20	内存使用	0.31 MiB

#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
#include<cstdio>
using namespace std;
typedef long long LL;
void gcd(LL a,LL n,LL &x,LL &y){
	if(n==0){
	x=1;y=0;
	return;	
	}
	gcd(n,a%n,x,y);
	LL tea=y,teb=x-y*(a/n);
	x=tea,y=teb;
	return;
}
LL g_cd(LL a,LL n){
	if(n==0)
	return a;
	return g_cd(n,a%n);
}
LL inv(LL a,LL n){
	LL x,y;
	gcd(a,n,x,y);
	return (x+n)%n;
}
LL mul_mod(LL a,LL b,LL n){
	return a*b%n;
}
LL fast_pow(LL a,LL b,LL n){
	LL ans=1;
	while(b){
		if(b&1){
			ans=mul_mod(ans,a,n);
		}
		a=mul_mod(a,a,n);
		b>>=1;
	}
	return ans;
}
LL baby_giant_step(LL a,LL b,LL p){
	LL m=sqrt(p+0.5);
	map<int,int>mp;
	for(int i=0;i<m;i++)
	mp[b]=i,b=b*a%p;
	LL x;
	for(int i=1;i<=m+1;i++){
		x=fast_pow(a,i*m,p);
		if(mp.count(x))return i*m-mp[x];
	}
	return -1;
}
LL call(LL a,LL b,LL n){
	a%=n,b%=n;
	LL x=g_cd(a,n);
	if(x==1){
		return baby_giant_step(a,b,n);
	}
	if(b%x)
	return -1;
	else{
	LL ans=call(a,b/x*inv(a/x,n/x),n/x);
	if(ans<0)
	return -1;
	return ans+1;
}
}
int main(){
	freopen("mitotic_division.in","r",stdin);
	freopen("mitotic_division.out","w",stdout);
	LL n;
	cin>>n;
	for(int i=0;i<n;i++){
		LL a,b,n;
		cin>>a>>b>>n;
		LL ans=call(a,b,n);
		if(ans<0){
			cout<<"no solution";
		}
		else cout<<ans;
		cout<<endl;
	}
}