大步小步/BSGS

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)

。

化简式子：

a^{i\times siz-j}\equiv b\pmod p

a^{i\times siz}\equiv b\times a^j\pmod p

因为

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

CPP

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_2=ax_1+b

x_3=ax_2+b=a(ax_1+b)+b

x_4=ax_3+b=a(a(ax_1+b)+b)+b

容易发现，

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

。

则：

aS=\sum\limits_{j=1}^{i-1}a^j

上式减下式：

S-aS=1-a^{i-1}

S(1-a)=1-a^{i-1}

S=\frac{1-a^{i-1}}{1-a}

我们回到刚刚的式子：

x_i=a^{i-1}x_1+b\times\frac{1-a^{i-1}}{1-a}

把

t

放进来：

t\equiv a^{i-1}x_1+b\times\frac{1-a^{i-1}}{1-a}\pmod p

t\equiv a^{i-1}x_1+\frac{b}{1-a}-a^{i-1}\frac{b}{1-a}\pmod p

t\equiv a^{i-1}(x_1-\frac{b}{1-a})+\frac{b}{1-a}\pmod p

(x_1-\frac{b}{1-a})a^{i-1}\equiv t-\frac{b}{1-a}

a^{i-1}\equiv\frac{t-\frac{b}{1-a}}{x_1-\frac{b}{1-a}}

然后就转化为了 BSGS 的板子了。容易发现当

a=0

或

a=1

的不能很好用这个式子解决，所以特判处理。部分细节看代码。

CPP

#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？

11\dots1

这样的数不好转化，若我们能将其表示为某个数的次幂就好了。想到了

99\dots9=10^i-1

，则

11\dots1=\frac{10^i-1}{9}

。

同余式子转化为：

\frac{10^i-1}{9}\equiv k\pmod p

，化简得

10^i\equiv9k+1\pmod p

，成功转化为了 BSGS 的样子。

好像要用 __int128 或者龟速乘，我选择 __int128。

文章操作

相关推荐

评论

大步小步/BSGS