BGGS模板

对于y^x=z(mod p)
判断y%p如果y%p是0的话那么没有答案,之后y%=p,z%=p如果z是1的话那么输出0剩下的就是正常的操作了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qpow(ll a,ll b,ll p)
{
	ll ans=1;
	ll base=a;
	while(b)
	{
		if(b&1)
		ans=ans%p*base%p,ans%=p;
		base=base%p*base%p,base%=p;
		b>>=1;
	}
	return ans%p;
}
void gcd(ll a,ll b,ll &x,ll &y)
{
	if(!b)
	x=1,y=0;
	else
	gcd(b,a%b,y,x),y-=a/b*x;
}
unordered_map<ll,ll> bk;
int main()
{
	ll t,k;
	scanf("%lld%lld",&t,&k);
	while(t--)
	{
		ll y,z,p;
		scanf("%lld%lld%lld",&y,&z,&p);
		if(k==1)
		printf("%lld\n",qpow(y,z,p)%p);
		else if(k==2)
		{
			ll d=__gcd(y,p),x0,y0;
			if(z%d)
			{
				printf("Orz, I cannot find x!\n");
				continue;
			}
			ll yy=y/d,pp=p/d,zz=z/d;
			gcd(y,p,x0,y0);
			printf("%lld\n",(x0*zz%pp+pp)%pp);
		}
		else
		{
			if(y%p==0)
			{
				printf("Orz, I cannot find x!\n");
				continue;
			}
			y%=p,z%=p;
			if(z==1)
			{
				printf("0\n");
				continue;
			}
			bk.clear();
			ll f=0,m=ll(sqrt(p)+1);
			for(ll i=0;i<m;i++)
			bk[(qpow(y,i,p)%p*z%p)%p]=i;
			for(ll i=1;i<=m;i++)
			if(bk[qpow(y,ll(i*m),p)])
			{
				printf("%lld\n",ll(i*m)-bk[qpow(y,ll(i*m),p)]);
				f=1;
				break;
			}
			if(!f)
			printf("Orz, I cannot find x!\n");
		}
	}
}

EXBSGS

typedef long long ll;
ll mul(ll a,ll b,ll p)
{
	return (a%p*b%p)%p;
}
ll bsgs(ll a,ll b,ll p)
{
	a%=p,b%=p;
    if(b==1) return 0;
    if(!b&&!a) return 1;
    if(!a) return -1;
    if(!b)
    {
        ll ret=0,d;
        while((d=__gcd(a,p))!=1)
        {
            ++ret,p/=d;
            if(p==1) return ret;
        }
        return -1;
    }
    ll ret=0,A=a,B=b,P=p,C=1,d;
    while((d=__gcd(A,P))!=1)
    {
        if(B%d) return -1;
        P/=d,B/=d;
        C=mul(C,A/d,P);
        ++ret;
        if(C==B) return ret;
    }
    bk.clear();
    ll f=1,t=sqrt((long long)P)+1;
    for(ll i=0;i<t;i++)
    {
        bk[mul(f,B,P)]=i;
        f=mul(f,A,P);
    }
    ll tf=f;
    f=mul(f,C,P);
    for(ll i=1;i<=t;i++)
    {
        if(bk[f]) return ret+i*t-bk[f];
        f=mul(f,tf,P);
    }
    return -1;
}