BSGS

大步小步算法

1.求解

其中 \(\gcd(a,p)=1\) ，解满足 \(0 \le x

令 \(x=A\left \lceil \sqrt p \right \rceil -B\) ，其中 \(0\le A,B\le \sqrt p\) ，则有 \(a^{A\left \lceil \sqrt p \right \rceil -B}\equiv b \pmod p\)

显然有 \(a^{A\left \lceil \sqrt p \right \rceil}\equiv b \times a^B \pmod p\)

枚举所有 \(B\) ，求出 \(ba^B\) 的所有可能取值，再枚举所有 \(A\) ，寻找有无对应值

#include 
#define int unsigned long long
using namespace std;

long long read()
{
	long long res=0,p=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-')p=-1; ch=getchar();}
	while(isdigit(ch)) res=res*10+ch-'0',ch=getchar();
	return res*p;
}

const int inf=2147483648;

int p,a,b;
int qp;
int x=inf;

map q;

long long qpow(long long x,long long y)
{
	long long t=1;
	while(y)
	{
		if(y&1) t=t*x%p;
		x=x*x%p,y/=2;
	} 
	return t;
}

signed main()
{
	p=read(),a=read(),b=read();
	a=a%p;
	if(!a)
	{
		cout<<"no solution";
		return 0;
	}
	int qp=sqrt(p)+1,t=1;
	for(int B=0;B<=qp;++B)
	{
		q[b*t%p]=B;
		t=t*a%p;
	}
	for(int A=0;A<=qp;++A)
	{
		long long now=qpow(a,A*qp%p);
		if(q.count(now))
		{
			int B=q[now];
			int xnow=A*qp-B;
			xnow=((xnow%p)+p)%p;
			x=min(x,xnow);
		}
	}
	if(x==inf) cout<<"no solution";
	else cout<