自动搬运

查看原文

来自洛谷，原作者为

	VenusM1nT 醉后不知天在水 满船清梦压星河 | 明日方舟群 348956527

搬运于2025-08-24 21:38:14，当前版本为作者最后更新于2018-12-28 08:50:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前两问都不难，这个$BSGS$还是比较难的……

我从隔壁的模板题复制的代码，所以写的是$ExBSGS$，比较冗长，虽然泛用性会更高，但是这题没有$P$点用……

对于第一问，直接套快速幂就行，$BSGS$要用到，就顺手解决了

对于第二问，扩欧求解，套费马小定理，数论渣表示一脸懵

对于第三问，$BSGS$硬上就行……

代码比较丑，凑合着看吧……

主程序还是挺简洁的$233$

#include<bits/stdc++.h>
#define ll long long
using namespace std;
map <ll,ll> m;
ll QuickPow(ll x,ll y,ll p)
{
	ll sum=1;
	while(y)
	{
		if(y&1) sum=sum*x%p;
		x=x*x%p;
		y>>=1;
	}
	return sum%p;
}
ll Gcd(ll x,ll y)
{
	return !x ? y : Gcd(y%x,x);
}
ll ExGCD(ll a,ll b,ll &x,ll &y)
{
	if(!b)
	{
		x=1;
		y=0;
		return a;
	}
	ll g=ExGCD(b,a%b,x,y);
	ll t=x;
	x=y;
	y=t-y*(a/b);
	return g;
}
ll BSGS(ll a,ll b,ll p,ll d)
{
	m.clear();
	b%=p;
	ll t=sqrt(p)+1,now=b,sum=d;
	for(int i=1;i<=t;i++)
	{
		now=now*a%p;
		m[now]=i;
	}
	now=QuickPow(a,t,p);
	for(int i=1;i<=t;i++)
	{
		sum=sum*now%p;
		if(m.count(sum)) return t*i-m[sum];
	}
	return -1;
}
int ExBSGS(int a,int b,int p)
{
	if(p==1) return 0;
	a%=p;
	b%=p;
	if(b==1) return 0;
	if(a==0)
	{
		if(b==0) return 1;
		return -1;
	}
	ll sum=1,tot=0;
	for(ll i=Gcd(a,p);i!=1;i=Gcd(a,p))
	{
		if(b%i) return -1;
		b/=i;
		p/=i;
		sum=sum*(a/i)%p;
		tot++;
		if(b==sum) return tot;
	}
	a%=p;
	ll cnt=BSGS(a,b,p,sum);
	if(cnt==-1) return -1;
	else return cnt+tot;
}
void Solve1()
{
	ll a,b,p;
	scanf("%lld %lld %lld",&a,&b,&p);
	printf("%lld\n",QuickPow(a,b,p));
}
void Solve2()
{
	ll a,b,p,x,y;
	scanf("%lld %lld %lld",&a,&b,&p);
	ll gcd=ExGCD(a,p,x,y);
	if(!(b%gcd))
	{
		ll t=p/gcd;
		x=(((x*b)/gcd)%t+t)%t;
		printf("%lld\n",x);
	}
	else printf("Orz, I cannot find x!\n");
}
void Solve3()
{
	ll a,b,p;
	scanf("%lld %lld %lld",&a,&b,&p);
	ll ans=ExBSGS(a,b,p);
	if(ans==-1) printf("Orz, I cannot find x!\n");
	else printf("%lld\n",ans);
}
int main()
{
	int Time,opt;
	scanf("%d %d",&Time,&opt);
	while(Time--)
	{
		if(opt==1) Solve1();
		else if(opt==2) Solve2();
		else if(opt==3) Solve3();
	}
	return 0;
}