bzoj 2242: [SDOI2011]计算器【扩展欧几里得+快速幂+BSGS】

第一问快速幂板子

第二问把式子转化为\( xy\equiv Z(mod\ P)\rightarrow xy+bP=z \)，然后扩展欧几里得

第三问BSGS板子

#include<iostream>

#include<cstdio>

#include<map>

#include<cmath>

using namespace std;

long long T,K,y,z,p;

map<long long,long long>mp;

long long gcd(long long a,long long b)

{

	return !b?a:gcd(b,a%b);

}

long long ksm(long long a,long long b,long long p)

{

	long long r=1ll;

	a%=p;

	while(b)

	{

		if(b&1)

			r=r*a%p;

		a=a*a%p;

		b>>=1;

	}

	return r;

}

void exgcd(long long a,long long b,long long &x,long long &y)

{

	if(!b)

	{

		x=1,y=0;

		return;

	}

	exgcd(b,a%b,y,x);

	y-=a/b*x;

}

int main()

{

	scanf("%lld%lld",&T,&K);

	while(T--)

	{

		scanf("%lld%lld%lld",&y,&z,&p);

		if(K==1)

			printf("%lld\n",ksm(y,z,p));

		else if(K==2)

		{

			//p=-p;

			long long t=gcd(y,p);

			if(z%t)

			{

				puts("Orz, I cannot find x!");

				continue;

			}

			y/=t,z/=t,p/=t;

			long long xx,yy;

			exgcd(y,p,xx,yy);

			printf("%lld\n",(xx*z%p+p)%p);

		}

		else

		{

			y%=p;

			if(!y&&!z)

			{

				puts("1");

				continue;

			}

			if(!y)

			{

				puts("Orz, I cannot find x!");

				continue;

			}

			mp.clear();

			long long m=ceil(sqrt(p)),t=1;

			mp[1]=m+1;

			for(long long i=1;i<m;i++)

			{

				t=t*y%p;

				if(!mp[t])

					mp[t]=i;

			}

			long long tmp=ksm(y,p-m-1,p),now=1,f=0;

			for(long long k=0;k<m;k++)

			{

				long long i=mp[z*now%p];

				if(i)

				{

					if(i==m+1)

						i=0;

					printf("%lld\n",k*m+i);

					f=1;

					break;

				}

				now=now*tmp%p;

			}

			if(!f)

				puts("Orz, I cannot find x!");

		}

	}

	return 0;

}

巴特西

bzoj 2242: [SDOI2011]计算器【扩展欧几里得+快速幂+BSGS】

最新文章

热门文章