今天刚学了个算法：BSGS算法（Baby-Step Giant-Step），即大步小步算法。常用于求解离散对数问题。
该算法可以在 \(O(\sqrt p)\) 的时间内求解形如：\(a^{x}\equiv b\pmod{p}\) 的高次同余方程。
问题：
P3846 [TJOI2007] 可爱的质数/【模板】BSGS
给定整数 \(a,b,p\) 互质，求满足 \(a^{x}\equiv b\pmod{p}\) 的最小非负整数解 \(x\)。
思路：
由扩展欧拉定理：\(a^{x}\equiv a^{x\mod\varphi(p)}\pmod{p}\)，
可知：\(a^{x}\) 在模 \(p\) 意义下的最小循环节为 \(\varphi\)，
由欧拉函数定义可知，\(\varphi(p)<p\)，因此 \(x\in[0,p]\)，一定可以找到最小整数 \(x\)。
暴力：
暴力枚举 \(0\) ~ \(p\) 中 \(x\) 的取值，时间复杂度：\(O(p)\)
BSGS算法：
令 \(x=im-j\)，其中 \(m=\lceil\sqrt p\rceil\)，\(i\in[1,m]\)，\(j\in[0,m-1]\)
当 \(i\) 取到最大值 \(m\)，\(j\) 取到最小值 \(0\) 时，\(x\) 取到最大值 \(m\times m=p\)
当 \(i\) 取到最小值 \(1\)，\(j\) 取到最大值 \(m-1\) 时，\(x\) 取到最小值 \(m-(m-1)=1\)
所以此时 \(x\in[1,p]\)，而 \(x=0\) 的情况只用特判一下就行了。
则：$$a^{im-j}\equiv b\pmod p$$
-
先枚举 \(j\)，将 \((ba^{j},j)\) 扔进哈希表中，若 \(ba^{j}\) 出现过，则用更大的 \(j\) 来更换原来的 \(j\)。（因为要求最小的 \(x\)，所以当 \(j\) 越大，\(x\) 就越小）
-
再枚举 \(i\)，计算 \((a^{m})^{i}\)，在哈希表中寻找相等的 \(ba^{j}\)，找到第一个就输出，此时 \(x=im-j\) 最小。
由于 \(i\) 和 \(j\) 的枚举都只用枚举 \(\sqrt p\) 次，因此时间复杂度：\(O(\sqrt p)\).
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL BSGS(LL a,LL b,LL p){
a%=p,b%=p;
if(b==1)return 0;//特判x=0的情况
LL m=ceil(sqrt(p)),t=b;
unordered_map<int,int>Hash;//哈希表
Hash[b]=0;
for(int j=1;j<m;j++){
t=t*a%p;//求b*a^j
Hash[t]=j;
}
LL mi=1;
for(int i=1;i<=m;i++)mi=mi*a%p;//求a^m
t=1;
for(int i=1;i<=m;i++){
t=t*mi%p;//求(a^m)^i
if(Hash.count(t))return i*m-Hash[t];
}
return -1;
}
int main(){
LL a,b,p;scanf("%lld%lld%lld",&p,&a,&b);
LL ans=BSGS(a,b,p);
if(ans==-1)puts("no solution");
else printf("%lld",ans);
return 0;
}