【[TJOI2007]可爱的质数】

题目

用一道板子题来复习一下(bsgs)

(bsgs)用于求解形如

[a^xequiv b(mod p) ]

这样的高次不定方程

由于费马小定理的存在，我们可是直接暴力扫一遍(p)，由于(p-1)次之后肯定会有循环节出现，所以(O(p))时间内就可以出解

(bsgs)本质上就是一种分块了

设(m=ceil(sqrt{p}))，我们设(x=i imes m-j)

显然我们只需要(i,jin[0,m])就可以令(x)表示([0,p])之间的所有数

现在我们的方程变成了这个样子

[frac{a^{i imes m}}{a^j}equiv b(mod p) ]

也就是

[a^{i imes m}equiv b imes a^j(mod p) ]

我们可以先开一个(hash)表，把所有(b imes a^j)，其中(jin[0,m])的值存下来

之后我们挨个检验(a^{i imes m})的值就好了，如果在(hash)表里找到和(a^{i imes m})相等的数，那么(i imes m-j)就是答案了

代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<tr1/unordered_map>
#define re register
#define LL long long
using namespace std::tr1;
unordered_map<LL,LL> ma;
LL a,b,P;
int m;
inline LL quick(LL a,LL b) {LL S=1;while(b) {if(b&1) S=S*a%P;b>>=1;a=a*a%P;}return S;}
int main()
{
	scanf("%lld%lld%lld",&P,&a,&b);
	m=ceil(std::sqrt(P));
	LL S=1,t=quick(a,m);
	for(re int i=0;i<=m;i++) ma[S*b%P]=i%P,S=S*a%P;
	S=t;
	for(re int i=1;i<=m;i++)
	{
		if(ma[S]) {LL ans=i*m-ma[S];printf("%d
",(ans%P+P)%P);return 0;}	
		S=S*t%P;
	}
	puts("no solution");
	return 0;
}