BZOJ 2480 Spoj3105 Mod

题目大意

求最小非负整数解$x$满足$a ^ x \equiv b (\text{mod }c)$

$gcd(a,c)$可以不为1，所以必须使用exBSGS.

注意$b = 1$的特殊情况。

#include <map>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
map<ll,ll>mp;
ll qpow(ll x,ll y,ll p)
{
	ll ret=1;
	while(y)
	{
		if(y&1) ret=ret*x%p;
		x=x*x%p,y>>=1;
 	}
 	return ret;
}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
ll calculate(ll a,ll m,ll b)
{
	a%=m,b%=m;
	if(b==1) return 0;
	ll ret=0,tmp=1,lim,i,t;
	for(ll g=gcd(a,m);g!=1;g=gcd(a,m))
	{
		if(b%g) return -1;
		b/=g,m/=g,tmp=tmp*a/g%m,++ret;
		if(b==tmp) return ret;
	}
	mp.clear();
	map<ll,ll>::iterator it;
	lim=ceil(sqrt(m));
	for(i=0,t=b;i<lim;++i,t=t*a%m)
		mp[t]=i;
	for(i=1,t=tmp,tmp=qpow(a,lim,m),t=t*tmp%m;i<=lim+1;++i,t=t*tmp%m)
	{
		it=mp.find(t);
		if(it!=mp.end())
			return i*lim-it->second+ret;
	}
	return -1;
}
int main()
{
	ll a,m,b,t;
	while(scanf("%lld%lld%lld",&a,&m,&b),a||m||b) 
	{
		if(m==1) {puts("0");continue;}
		t=calculate(a,m,b);
		if(t==-1) puts("No Solution");
		else printf("%lld\n",t);
	}
	return 0;
}