大步小步/BSGS

lunivia · 2025-07-28 19:14:07 · 算法·理论

BSGS 全称为 baby step giant step，用于求最小的 x 满足 a^x\equiv b\pmod p。

主要思路基于分块与哈希。

首先我们知道若 \gcd(a,p)=1，那么满足 a^p\equiv a \pmod p（费马小定理）。所以这意味着若有答案，则 x 一定小于 p。

显然暴力枚举是不可行的，而 BSGS 算法基于分块使时间复杂度降低到了根号级别，可以通过。

具体而言，令 siz=\lceil\sqrt n\rceil（防止未全部覆盖），则 x 可以表示为 i\times siz-j,j\in[0,siz)。

化简式子：

因为 i,j 的范围都在 [0,siz) 之间（i 的范围是因为 i\times siz\le p），所以我们考虑暴力预处理出每个 j 对应的 b\times a^j\bmod p，再把每个元素放到桶里，枚举每个 i，找到对应的 j，最终答案即为最先找到的 i\times siz-j（由于 i 越小 i\times siz-j 越小）。时间复杂度为 \Theta(\sqrt n)。

具体实现，hash 我选择 unordered_map，速度接近 \Theta(1)。

P3846 [TJOI2007] 可爱的质数/【模板】BSGS

int BSGS(int a,int b,int p) {
  if(b == 1) return 0; //几个特判
  if(a % p == b % p) return 1;
  if(a % p == 0) return -1;
  unordered_map<int,int> hash;
  int siz = ceil(sqrt(p));
  for(int i = 0,base = b % p;i <= siz;i++) hash[base] = i,base = base * a % p;  //预处理任意j对应的结果
  for(int i = 1,base = Pow(a,siz,p),tmp = 1;i <= siz;i++) {
    tmp = tmp * base % p;
    if(hash[tmp]) return (i * siz - hash[tmp]) % p; //容易发现i*siz-hash[tmp]>=0，所以无需+p再%p
  }
  return -1;
}

P2485 [SDOI2011] 计算器

拼好题，第一问用快速幂，第二问求 x\times inv(y)\bmod p，第三问 BSGS 板子。

P3306 [SDOI2013] 随机数生成器

题意：求最小的 i 满足 x_i\equiv t\pmod p。

观察式子，是一个递推的形状，：

容易发现，x_i=a^{i-1}x_1+b\sum\limits_{j=0}^{i-1}a^j。

接下来是等比公式的相关应用，学过的可以跳过。

令 S=\sum\limits_{j=0}^{i-2} a^j。

则：

上式减下式：

我们回到刚刚的式子：

把 t 放进来：

然后就转化为了 BSGS 的板子了。容易发现当 a=0 或 a=1 的不能很好用这个式子解决，所以特判处理。部分细节看代码。

#include <bits/stdc++.h>
using namespace std;

template<class T>T Pow(T a,T b,T p){T ans=1;for(;b;b/=2){ans=((b&1?a:1)*ans%p),a=a*a%p;}return ans;}
template<class T>T Inv(T a,T b){return Pow(a,b-2,b);}

#define int long long 

const int _ = 1e5 + 5;

int BSGS(int a,int b,int p) {
  unordered_map<int,int> hash;
  int siz = ceil(sqrt(p));
  for(int i = 0,base = b % p;i <= siz;i++) hash[base] = i,base = base * a % p;
  for(int i = 1,base = Pow(a,siz,p),tmp = 1;i <= siz;i++) {
    tmp = tmp * base % p;
    if(hash[tmp]) return ((i * siz - hash[tmp]) % p + p) % p;
  }
  return -1;
}

void solve() {
  int p,a,b,x,t;
  cin >> p >> a >> b >> x >> t;
  if(x == t) { //相等直接输出1
    cout << 1 << '\n';
  } else if(a == 0) { //a=0时b=t
    cout << (b == t ? 2 : -1) << '\n';
  } else if(a == 1) { //a=1时注意答案是p的话就不要再取模了
    t = ((t - x) % p + p) % p;
    if(t % __gcd(b,p)) cout << -1 << '\n';
    else {
      if((t * Inv(b,p) + 1) % p == 0) cout << p << '\n';
      else cout << (t * Inv(b,p) + 1) % p << '\n';
    }
  } else {
    int inv = Inv(1 - a,p);
    int ans = BSGS(a,((t - inv) % p + p) % p * Inv(((x - inv) % p + p) % p,p),p) % p;
    if(ans == -1) cout << -1 << '\n';
    else cout << ans + 1 << '\n';
  }
}

signed main() {
  int tt;
  cin >> tt;
  while(tt--) solve();
  return 0;
}

P4884 多少个 1？