简介
大步小步(Baby Step Giant Step)算法，可以在 \(O(\sqrt{p}\cdot f(p))\) 的时间复杂度内（\(f(p)\) 为一个大小为 \(p\) 的映射结构（如 map、hash table）进行单次读取 / 随机访问 的时间复杂度）内解下列关于 \(x\) 的方程（离散对数方程）：
\[a^{x}\equiv b\pmod{p} \]
其中 \(\mathbf{p\in\mathbb{P},a\perp p}\)。
思路
由于欧拉定理 \(a\perp p,a^{b}\equiv a^{b\bmod \varphi(p)}\pmod{p}\)，可以得到：
\[a^{x \bmod (p-1)}\equiv a^{x}\pmod{p} \]
因此我们有一个 \(O(p)\) 的算法。但这还不够。
考虑以 \(B=O(\sqrt{p})\) 为块长分块，令解 \(x=iB-j\)。则：
\[\begin{aligned} &a^{iB+j}\equiv b\pmod{p}\\ &(a^{B})^{i}\div a^{j}\equiv b\pmod{p}\\ &\because a\perp p\\ &\therefore(a^{B})^{i}\equiv a^{j}b\pmod{p} \end{aligned} \]
然后，我们用一个映射结构记录一下 \(a^{j}\bmod p\) 对应的 \(j\)。然后枚举 \(i\) 找映射里有没有 \(((a^{B})^{i}\cdot b^{-1})\bmod p\) 即可。找逆元可以用费马小定理。
P3846 [TJOI2007] 可爱的质数/【模板】BSGS
模板题，不解释。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int pow(int a,int b,const int &mod){
int ans=1;
for(;b;b>>=1,a=1ll*a*a%mod){
if(b&1)ans=1ll*ans*a%mod;
}
return ans;
}
int BSGS(int a,int b,const int &p){
int blk=sqrt(p);
map<int,int> mmap;mmap[1]=0;
int apw=1;
for(int i=1;i<=blk;i++){
apw=apw*a%p;
mmap[apw]=i;
}
int pw=1,Q=pow(a,blk,p),invb=pow(b,p-2,p);
for(int i=1;i<=blk;i++){
pw=pw*Q%p;
if(mmap.count(pw*invb%p)) return i*blk-mmap[pw*invb%p];
}
return -1;
}
signed main(){
int p,b,n;
cin>>p>>b>>n;
int ret=BSGS(b,n,p);
if(ret==-1) cout<<"no solution";
else cout<<ret;
return 0;
}