记录编号	230845	评测结果	AAAAAAAAAA
题目名称	多-有丝分裂	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.406 s
提交时间	2016-02-24 12:36:46	内存使用	8.59 MiB

#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#define N 70000
using namespace std;
typedef long long ll;
ifstream cin("mitotic_division.in");
ofstream cout("mitotic_division.out");
ll add=0;
ll INF=1;
ll splay;
int T;
int cnt=0;
map<ll,int > F;
class Hash_table
{
public:
	ll num[10];
	int o[10];
	int top;
}a[N+10];
ll find(ll x)
{
	ll fir,sec;
	int i;
	fir=x%67481;
	sec=x%99991;
	for(i=1;i<=a[fir].top;i++)
	{
		if(sec==a[fir].o[i])return a[fir].num[i];
	}
	return 0;
}
void insert(ll x,ll y)
{
	ll fir,sec;
	int i;
	fir=x%67481;
	sec=x%99991;
	for(i=1;i<=a[fir].top;i++)
	{
		if(sec==a[fir].o[i])
		{
			a[fir].num[i]=y;
			return ;
		}
	}
	a[fir].top++;
	a[fir].num[a[fir].top]=y;
	a[fir].o[a[fir].top]=sec;
	//for(i=1;i<=top;i++)
}
void clear(ll x)
{
	ll fir;
	fir=x%67481;
	a[fir].top=0;
}
ll gcd(ll x,ll y)
{
	while(true)
	{
		if(!x)return y;
		if(!y)return x;
		if(x>y)x%=y;
		else y%=x;
	}
}
ll pow(ll a,ll x,ll p)//a^x mod p
{
	ll c=1;
	while(x)
	{
		if(x&1)c=(c*a)%p;
		a=(a*a)%p;
		x=x>>1;
	}
	return c;
}
void exgcd(ll a,ll b,ll &x,ll &y)//a mod b=1  求逆元
{
	if(!b)
	{
		x=1;
		y=0;
	}
	else
	{
		exgcd(b,a%b,x,y);
		ll t;
		t=x;
		x=y;
		y=t-(a/b)*x;
	}
}
void cleard(ll a,ll b,ll c)
{
	ll i,temp,mor;
	temp=b;
	for(i=1;i<splay;i++)
	{
		temp*=a;
		temp%=c;
		clear(temp);
	}
}
ll work(ll a,ll b,ll c)//真大步小步算法
{
	ll i,temp,mor;
	temp=b;
	//F.clear();
	for(i=1;i<splay;i++)
	{
		temp*=a;
		temp%=c;
		insert(temp,i);
		//F[temp]=i;
	}
	temp=pow(a,splay,c);
	mor=1;
	for(i=1;i<=splay+2;i++)
	{
		mor*=temp;
		mor%=c;
		if(find(mor))return i*splay-find(mor);
		//if(F[mor])return i*splay-F[mor];
		if(mor==b)return i*splay;
	}
	return INF;
}
ll baby_grant(ll a,ll b,ll c)//a^x mod c=b
{
	ll d,x,y,ans;
	add=0;
	//方程转化，使得c为质数或b=1
	d=gcd(a,c);
	while(d!=1)
	{
	    if(c!=1)
	    {
		   a%=c;
		   b%=c;
	    }
	    if(b%d!=0)return INF;//b不整除d,无解
		   b/=d;c/=d;
	       exgcd(a/d,c,x,y);
		   if(x<=0)x+=c;//求逆元
	       b*=x;
	       if(c!=1)
		   {
			   a%=c;
			   b%=c;
		   }
	       add++;
		   d=gcd(a,c);
	}
	splay=ll(sqrt(double(c)));
	ans=work(a,b,c);
	cleard(a,b,c);
	return ans;
}
int main()
{
	ll a,b,c,ans;
	int T;
	INF=INF<<60;
	cin>>T;
	while(T--)
	{
		cin>>a>>b>>c;
		ans=baby_grant(a,b,c);
		if(ans<=INF/100)cout<<ans+add<<endl;
		else cout<<"no solution"<<endl;
	}
	return 0;
}