#include<cstdio>
#include<algorithm>
#include<cmath>
#include<algorithm>
#include<vector>
#include<utility>

__int64		x,y,z,k,base;
std::vector<std::pair<int,int> >	q;

void	init()
{
	int		i;
	__int64	t;	
	
	
	scanf("%I64d %I64d %I64d\n",&x,&z,&k);
	if ((!x)&&(!z)&&(!k))
		exit(0);
	k=(k%z+z)%z;
	
	base=(int)sqrt(z)+1;
	q.clear();
	
	t=1;
	for (i=0;i<base;i++)
	{	
		q.push_back(std::make_pair(t,i));
		t=(t*x)%z;
	}
	
	std::sort(q.begin(),q.end());
}

__int64		mod_exp(__int64	a,__int64	b,__int64	n)
{
	__int64	d;
	
	d=1;
	while ((b>0)&&(a!=1))
	{
		if (b&1) d=(d*a)%n;
		b=b>>1;
		a=(a*a)%n;
	}
	return (d);
}

void	ext_gcd(__int64	a,__int64	b,__int64	&x,__int64	&y,__int64	&d)
{
	__int64	tx,ty;
	
	if (b==0)
	{
		x=1;
		y=0;
		d=a;
		return;
	}
	
	ext_gcd(b,a%b,tx,ty,d);	
	x=ty;
	y=tx-(a/b)*ty;
}

int		find(int		p)
{
	std::vector<std::pair<int,int> >::iterator	t;
		
	t=std::lower_bound(q.begin(),q.end(),std::make_pair(p,-1));
	if ((t==q.end())||((*t).first!=p))
		return(base);
	else
		return((*t).second);
}

bool	starmain()
{
	__int64		a,ty,tx,d,ttt,t;	
	
	for (y=0;y<z;y+=base)
	{
		a=mod_exp(x,y,z);
		ext_gcd(a,z,tx,ty,d);		
		if (k%d==0)
		{
			ttt=z/d;
			tx=((tx*k/d)%ttt+ttt)%ttt;			
				
			if ((t=find(tx))<base)
			{
				y+=t;
				return(true);
			}	
		}
	}	
	
	return(false);
}


int		main()
{
//	freopen("c:\\in.txt","r",stdin);
	
	while (true)
	{			
		init();
		if (starmain())
			printf("%I64d\n",y);
		else
			printf("No Solution\n");
	}
	
	return(0);
}

• 貌似这样的算法过不了 (1828) ecjtubaowp 2007-07-22 14:40:59
  • Re:貌似这样的算法过不了 (4) gaosimeng 2007-07-23 07:45:02