大步小步

标签：pmod 小步 sqrt 大步 ll 根号 equiv

大步小步算法是一种可以在\(O(\sqrt{p})\)的时间内求出形如 \(a^x \equiv b \pmod{p}\)或 \(x^a \equiv b \pmod{p}\)的算法，其实思想异常的简单，这里介绍一下第一种

我们发现，$a^{\phi(p)} $ ~ \(a^{1}\) 之间的结果包含了所有的可能模数结果，所以我们通过人类智慧进行根号平衡

我们设 \(q=\sqrt{p}+1\)，则发现，所有小于根号的结果我们可以直接爆算，所有大于根号的结果我们可以像分块那样预处理出来

所以大步小步其实就是数论意义上的分块？

说一下具体算法流程

我们先暴力预处理一下零散块的答案，然后把他挪到柿子右边，像这样

(这里设总块数为 \(i\)，零散块为 \(j\)，块长为 \(t\)

\[a^{i*t-j} \equiv b \pmod p\\ a^{i*t} \equiv b \,*\, a^j \]

这一步变形的前提是 \(a\) 与 \(p\) 互质，才能推出来这一步，否则，要用到 EX-BSGS

接下来的事情好办了，我们对于每一个 \(j\) 预处理出来 \(a^j \, * \, b \pmod p\)，然后枚举大块的块数，验证一下就好了

复杂度 \(O(\sqrt{p})\)

#include <iostream>
#include <map> 
#define ll long long


using namespace std;
ll a,b,p;
map<ll,ll>hsh;

void bsgs(){
	ll t;
	for(t=1;t*t<=p;++t) ;
	--t;
	ll tmp=1;
	hsh[0]=b;
	for(int i=1;i<t;++i)
		tmp=(tmp*a)%p,hsh[(b*tmp)%p]=i;
	if(a==0){
		if(b==0) cout << 1  << endl;
		else cout << "no solution" << endl;
		return ;
	} 
	tmp=(tmp*a)%p;
	ll q=1;
	for(int i=1;i<=t;++i){
		q=(tmp*q)%p;
		if(hsh.find(q)!=hsh.end()) {
			cout << i*t-hsh[q] << endl;
			return ;
		}
	}
	cout << "no solution" << endl;
		
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0); 
	cin >> p >> a >> b;
	bsgs();
	
	return 0;
} 

标签：pmod,小步,sqrt,大步,ll,根号,equiv
From： https://www.cnblogs.com/Benzenesir/p/17227920.html