\(\\\)

BSGS

用于求解关于 \(x\) 的方程：

\[a^x\equiv b\pmod p\ ,\ (p,a)=1
\]

一般求解的是模意义下的指数，也就是最小非负整数解。

\(\\\)

算法思想

本质是双向搜索，或阈值优化的思想。

首先设"步幅" 为 \(m=\lceil{ \sqrt p}\rceil\) ，然后将方程写作

\[a^{i\times m-j}\equiv b\pmod p
\]

其中 \(i\) 就是所谓"大步"， \(j\) 就是所谓"小步"，我们要把他们组合在一起。

直接搜索两个数不如折半搜索一个数，然后再组合。

于是我们可以将分母上的 \(a^j\) 移项，得到

\[a^{i\times m}\equiv b\times a^j\pmod p
\]

然后就成了比较标准的双向搜索形式。

先把右一半的答案记下来，然后拿左一半搜到的每一个数去查询是否出现过就好了。

\(\\\)

代码实现

对于每一个 \(j\in [0,m-1]\) ，将 \(b\times a^j\ \%\ p\) 的答案放到哈希表里。

然后对于每一个 \(i\in[1,m](\) 此范围依据定义而来，尤其注意！\()\)，去哈希表里查是否有 \(a^{im}\ \%\ p\) 的值。

还有两个小优化：

注意到求出为同一个值的 \(j\) ，因为在答案里系数为 \(-1\) ，所以对于求出最小解 \(j\) 肯定是越大越优秀。

因此再哈希表里插入相同的值时，可以直接取 \(max\)，如果是按序插入直接覆盖即可。

这里也延申出了一种做法，直接用 \(map\) 存储结果，将结果映射到 \(j\) ，按序插入直接覆盖，复杂度多个\(log\) 。
运算过程中只需一次快速幂。

一开始每一次都是乘上 \(a\) ，所以一遍循环一遍乘即可，第二步同理，只需题前计算出 \(a^m\) 的值。

这一优化在需要快速乘的时候效果很好。

我们以 [TJOI2007]可爱的质数一题为例提供一份模板。

#include<map>

#include<cmath>

#include<cstdio>

#include<cctype>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define R register

using namespace std;

typedef long long ll;

map<ll,ll> s;

inline ll qpow(ll x,ll t,ll p){

  ll res=1;

  while(t){

    if(t&1) (res*=x)%=p;

    (x*=x)%=p; t>>=1;

  }

  return res;

}

inline ll BSGS(ll a,ll b,ll p){

  b%=p;

  ll m=ceil(sqrt(p));

  for(R ll i=0;i<m;++i,(b*=a)%=p) s[b]=i;

  a=qpow(a,m,p);

  for(R ll i=1,tmp=a;i<=m;++i,(tmp*=a)%=p)

    if(s.find(tmp)!=s.end()){

      if(i*m<s[tmp]) continue;

      return i*m-s[tmp];

    }

  return -1;

}

int main(){

  ll a,b,p;

  scanf("%lld%lld%lld",&p,&a,&b);

  ll x=BSGS(a,b,p);

  if(x>=0) printf("%lld\n",x);

  else puts("no solution");

  return 0;

}

巴特西

大步小步法(BSGS) 学习笔记

BSGS

算法思想

代码实现

最新文章

热门文章