BZOJ2242[SDOI2011]计算器——exgcd+BSGS

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int T,k;
ll y,z,p;
ll G;
map<ll,int>ind;
ll quick(ll x,ll y,ll mod)
{
	ll res=1ll;
	while(y)
	{
		if(y&1)
		{
			res=res*x%mod;
		}
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
ll gcd(ll x,ll y)
{
	return y==0?x:gcd(y,x%y);
}
void exgcd(ll x,ll y,ll &a,ll &b)
{
	if(!y)
	{
		a=1,b=0;
		return ;
	}
	exgcd(y,x%y,b,a);
	b-=(x/y)*a;
}
void solve(int opt)
{
	if(opt==1)
	{
		printf("%lld\n",quick(y,z,p));
	}
	else if(opt==2)
	{
		y%=p,z%=p;
		ll d=gcd(y,p);
		if(z%d)
		{
			printf("Orz, I cannot find x!\n");
			return ;
		}
		y/=d,z/=d,p/=d;
		ll a,b;
		exgcd(y,p,a,b);
		a*=z;
		a=(a%p+p)%p;
		printf("%lld\n",a);
	}
	else
	{
		ll n=ceil(sqrt(p));
		if(y%p==0&&z)
		{
			printf("Orz, I cannot find x!\n");
			return ;
		}
		ind.clear();
		ll sum=z%p;
		ind[sum]=0;
		for(ll i=1;i<=n;i++)
		{
			sum=sum*y;
			sum%=p;
			ind[sum]=i;
		}
		sum=quick(y,n,p);
		ll num=1ll;
		for(int i=1;i<=n;i++)
		{
			num*=sum,num%=p;
			if(ind.find(num)!=ind.end())
			{
				printf("%lld\n",((n*i-ind[num])%p+p)%p);
				return ;
			}
		}
		printf("Orz, I cannot find x!\n");
	}
}
int main()
{
	scanf("%d%d",&T,&k);
	while(T--)
	{
		scanf("%lld%lld%lld",&y,&z,&p);
		solve(k);
	}
}