BZOJ 2242 [SDOI2011]计算器

题目大意

求三个方程的最小非负整数解。

1. $x = y ^ z \mod p$
2. $x y \equiv z (\text{mod }p)$
3. $y ^ x \equiv z (\text{mod }p)$

第一问快速幂，第二问exGCD，第三问BSGS.

我当时还不是很了这个算法，所以写的和笔记描述的不一致。与笔记一致的题解

#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;
}
void extGCD(ll a,ll b,ll &d,ll &x,ll &y) {
	if(!b) d=a,x=1,y=0;
	else extGCD(b,a%b,d,y,x),y-=x*(a/b);
}
void BSGS(ll a,ll b,ll c)
{
	mp.clear();
	ll m=ceil(sqrt(c)),i,t,u=qpow(a,c-m-1,c);
	if(!u)
	{
		puts("Orz, I cannot find x!");
		return;
	}
	map<ll,ll>::iterator it;
	for(i=0,t=1;i<m;++i,t=t*a%c) if(mp.find(t)==mp.end()) mp[t]=i;
	for(i=0,t=1;i<m;++i,t=t*u%c)
	{
		it=mp.find(b*t%c);
		if(it!=mp.end())
		{
			printf("%lld\n",i*m+it->second);
			return;
		}
	}
	puts("Orz, I cannot find x!");
	return;
}
int main()
{
	ll y,z,p;
	int T,opt;
	scanf("%d%d",&T,&opt);
	while(T--)
	{
		scanf("%lld%lld%lld",&y,&z,&p);
		switch(opt)
		{
			case 1:printf("%lld\n",qpow(y,z,p));break;
			case 2:
			{
				ll td,tx,ty;
				extGCD(y,p,td,tx,ty);
				if(z%td) puts("Orz, I cannot find x!");
				else printf("%lld\n",((tx*z/td)%p+p)%p);
				break;
			}
			case 3:BSGS(y,z,p);break;
		}
	}
	return 0;
}