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

#include<cstdio>
#include<cstring>
#include<map>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
LL A,B,C;
LL pow(LL a,LL k,LL p)
{
	LL ans=1;
	for (;k;k>>=1)
	{
		if (k&1)
			ans=ans*a%p;
		a=a*a%p;
	}
	return ans;
}
LL baby_giant_step(LL a,LL b,LL p)
{
//	cout<<"baby:"<<a<<" "<<b<<" "<<p<<endl;
	map<LL,LL> pw;
	LL m=sqrt(p+0.5);
	for (int i=0;i<m;++i)
		pw[b]=i,b=b*a%p;
	for (int i=1;i<=m+1;++i)
	{
		LL x=pow(a,i*m,p);
//		cout<<i<<" "<<x<<endl;
		if (pw.count(x))
			return i*m-pw[x];
	}
	return -1;
}
LL gcd(LL a,LL b)
{
	return b==0?a:gcd(b,a%b);
}
void ex_gcd(LL a,LL b,LL &x,LL &y)
{
	if (!b)
		x=1,y=0;
	else
		ex_gcd(b,a%b,y,x),y-=(a/b)*x;
}
LL inv(LL a,LL p)
{
	LL x,y;
	ex_gcd(a,p,x,y);
//	cout<<"inv:"<<a<<" "<<p<<" : "<<(x%p+p)%p<<endl;
	return (x%p+p)%p;
}
LL calc(LL a,LL b,LL c)
{
	LL g=gcd(a,c);
//	cout<<"calc:"<<a<<" "<<b<<" "<<c<<" -> "<<g<<endl;
	if (g==1)
		return baby_giant_step(a,b,c);
	if (b%g)
	{
//		cout<<b<<" can't divide "<<g<<endl;
		return -1;
	}
	else
	{
//		cout<<"----------"<<((b/g)%c)*inv(a/g,c/g)<<endl;
		LL ans=calc(a,((b/g)%c)*inv(a/g,c/g),c/g);
		if (ans==-1)
			return -1;
		else
			return ans+1;
	}
}
int main()
{
//	freopen("c.in","r",stdin);
//	freopen("c.out","w",stdout);
	freopen("mitotic_division.in","r",stdin);
	freopen("mitotic_division.out","w",stdout);
	int t;
	cin>>t;
	while (t--)
	{
		scanf("%lld%lld%lld",&A,&B,&C);
		LL ans=calc(A,B,C);
		if (ans==-1)
			printf("no solution\n");
		else
			printf("%lld\n",ans);
	}
	return 0;
}