BSGS 学习笔记
MY（一名蒟蒻）
·
·
个人记录
Baby Step, Giant Step 算法
BSGS 基础篇
又名北上广深，拔山盖世算法。用来求解高次同余方程。
高次同余方程有 a^x \equiv b\pmod p 和 x^a \equiv b\pmod p ，两类问题。由于作者太菜，这里只讨论前者。
P3846 [TJOI2007] 可爱的质数/【模板】BSGS
问题描述：给定一个质数 p ，以及一个整数 a，一个整数 b ，求出最小的非负整数 x 满足 a^x \equiv b\pmod p 。
Solution
设 x=i\times t-j ，其中 t=\lceil \sqrt p \rceil,0\leq j \lt t ，则方程等价于 a^{i\times t-j} \equiv b \pmod p \ \Leftrightarrow\ (a^t)^i \equiv b\times a^j 。
对于所有 $i$ 的可能取值 $i\in\lbrack 0,t \rbrack$ ，搞出 $(a^t)^i \bmod p$ ，在 Hash 表里查是不是有对应的 $j$ 更新答案即可。
时间复杂度 $O(\sqrt n)$ ， Hash 表使用 map 则多一个 $\log$ 。
那么前面的预处理就是 Baby Step ，后面的查找就是 Giant Step 。
---
以下是 BSGS 的实现。
```cpp
map <int,int> hash;
int BSGS(int a,int b,int p)
{
b%=p;
int t=sqrt(p)+1,val=1;
for(int i=0;i<t;i++)
{
hash[1ll*b*val%p]=i;
val=1ll*val*a%p;
}
a=val; val=1;
if(!a) return !b? 1:-1;//特判等于0的情况
for(int i=0,j;i<=t;i++)
{
j=hash.find(val) == hash.end()? -1:hash[val];
if(~j && i*t-j >= 0) return i*t-j;//满足条件返回
val=1ll*val*a%p;
}
return -1;
}
```
从小到大枚举，及时返回。
注意在算乘方的时候使用快速幂复杂度会非常假，从小到大顺便乘可以保证正确的复杂度。
---
[P2485 [SDOI2011]计算器](https://www.luogu.com.cn/problem/P2485)
第一问快速幂，第二问求个逆元，第三问 BSGS 。
这题不知道哪个毒瘤地方要开 long long 。
[P4454 [CQOI2018]破解D-H协议](https://www.luogu.com.cn/problem/P4454)
由于原根的性质，随便选一组求解然后快速幂即可。
[题解](https://www.luogu.com.cn/blog/nizhuan/solution-p4454)
[P3306 [SDOI2013] 随机数生成器](https://www.luogu.com.cn/problem/P3306)
给了一个递推式 $f_n=a\times f_{n-1}+b$ 。
这里讲一下如何用待定系数法求通项公式。
令递推式两边同时加上一个常数 $t$ 构造一个公比为 $a$ 的等比数列。即 $f_n+t=a(f_{n-1}+t)$ ，展开后联立上式解得 $t=\frac{b}{a-1}$ 。
得 $f_n=a^{n-1}\times (f_1+\frac{b}{a-1})-\frac{b}{a-1}$ 。
题目给出的条件中，未知的只有 $n$ ，移项后对于 $a^{n-1}$ 这东西跑 BSGS 求解 $n$ 。
注意到当 $a\leq 1$ 时，通项公式无意义。所以要特判。
### Code
```cpp
//f(n)+b/(a-1)=(f(1)+b(a-1))*a^(n-1)
//注意随时取模
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
inline int qpow(int x,int y,int p)
{
int res=1;
while(y)
{
if(y&1) res=1ll*res*x%p;
y>>=1; x=1ll*x*x%p;
}
return res;
}
map <int,int> _hash;
inline int BSGS(int a,int b,int p)
{
b%=p; _hash.clear();
int t=sqrt(p)+1,val=1;
for(int i=0;i<t;i++)
{
_hash[1ll*b*val%p]=i;
val=1ll*val*a%p;
}
a=val; val=1;
if(!a) return !b? 1:-2;
for(int i=0,j;i<=t;i++)
{
j=_hash.find(val) == _hash.end()? -1:_hash[val];
if(~j && i*t-j >= 0) return i*t-j;
val=1ll*val*a%p;
}
return -2;
}
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
int p,a,b,x1,t,T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d%d",&p,&a,&b,&x1,&t);
a%=p; b%=p;
if(x1 == t) {puts("1"); continue ;}//第一天读到直接输出1，联系BSGS求解的内容可知求解过程中会出错
if(a == 0) {puts(b == t? "2":"-1"); continue ;}//常数列
if(a == 1 && !b) {puts("-1"); continue ;}//等差数列
if(a == 1)
{
printf("%d\n",1ll*((t-x1)%p+p)*qpow(b,p-2,p)%p+1);
continue ;
}
t+=1ll*b*qpow(a-1,p-2,p)%p;
t=1ll*t*qpow((x1+1ll*b*qpow(a-1,p-2,p))%p,p-2,p)%p;
printf("%d\n",BSGS(a,t,p)+1);
}
// fclose(stdin); fclose(stdout);
return 0;
}
```
[P4884 多少个1？](https://www.luogu.com.cn/problem/P4884)
还是一个递推式 $f_n=10\times f_{n-1}+1$ 且 $f_1=1$。
通项公式 $f_n=10^{n-1}\times (1+\frac{1}{9})-\frac{1}{9} \ \Leftrightarrow \ f_n=\frac{10^n-1}{9}$ 。
数据范围很大，乘的时候会爆 long long ，需要用快速乘。
~~我这个菜鸡快速乘竟然初始了个 `res=1` 。~~
本题保证有解。
[P4861 按钮](https://www.luogu.com.cn/problem/P4861)
题目只关心个位，于是转化为求 $K^{x} \equiv 1 \pmod m$ 。
并没有说 $K$ 与 $m$ 互质，但是考虑无解的情况，当且仅当 $K$ 与 $m$ **不互质**。
**证明：**
以上同余方程等价于不定方程 $K\times K^{x-1}-a\times m=1$ 。
有解时**满足裴蜀定理**，所以 $\gcd(K,m)=1$ 。
也就是 $K$ 与 $m$ **互质**。
输入时先判断一下是否有解，有解再跑 BSGS 。
[题解](https://www.luogu.com.cn/blog/nizhuan/solution-p4861)
---
## 拓展篇 exBSGS ~~恶心BSGS~~
[OI Wiki](https://oi-wiki.org/math/bsgs/#_8)
~~咋啥东西都有 ex~~ 。
[P4195 【模板】扩展 BSGS/exBSGS](https://www.luogu.com.cn/problem/P4195) [题解](https://www.luogu.com.cn/blog/nizhuan/solution-p4195)
[SP3105 MOD - Power Modulo Inverted](https://www.luogu.com.cn/problem/SP3105) [题解](https://www.luogu.com.cn/blog/nizhuan/solution-sp3105)
好耶，紫色的双倍经验！
$a^x \equiv b\pmod p
还是这个方程，普通的 BSGS 只能解决 a 与 p 互质的情况，而 exBSGS 不需要这个条件。
不互质咋办？变成互质！
方程两边同时除以 \gcd(a,p) ，注意模数 p 也要除，若 \gcd(a,p) \nmid b 则无解。
若仍不互质则重复进行上述过程，直至 p 与方程的左边互质。
记 d 为每次的 \gcd 的乘积，一共除了 cnt 次，则方程转化为：
\frac{a^{cnt}}{d}\times a^{x-cnt} \equiv \frac{b}{d}\pmod {\frac{p}{d}}
因为 a\perp \frac{p}{d} ，所以 \frac{a^{cnt}}{d} 在 \bmod \frac{p}{d} 意义下有逆元，移项求解 x-cnt 然后加上 cnt 即可。
当然有时候 x=cnt ，这种情况直接返回 cnt 就好了。
exBSGS 代码实现
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
if(!b) {x=1; y=0; return a;}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
map <int,int> _hash;
inline int exBSGS(int a,int b,int p)
{
a%=p; b%=p;
if(b == 1 || p == 1) return 0;
int d,ax=1,cnt=0,x,y;
while((d=exgcd(a,p,x,y))^1)
{
if(b%d) return -1;
b/=d; p/=d; cnt++;
ax=1ll*ax*(a/d)%p;
if(ax == b) return cnt;
}
exgcd(ax,p,x,y);
int inv=(x%p+p)%p;
b=1ll*b*inv%p;
// BSGS
_hash.clear();
int t=ceil(sqrt(p)),val=1;
for(int i=0;i<t;i++)
{
_hash[1ll*b*val%p]=i;
val=1ll*val*a%p;
}
a=val; val=1;
if(!a) return !b? 1+cnt:-1;
for(int i=0,j;i<=t;i++)
{
j=_hash.find(val) == _hash.end()? -1:_hash[val];
if(~j && i*t-j >= 0) return i*t-j+cnt;
val=1ll*val*a%p;
}
return -1;
}
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
int a,b,p,ans;
while(scanf("%d%d%d",&a,&p,&b) == 3 && a && b && p)
{
ans=exBSGS(a,b,p);
if(~ans) printf("%d\n",ans);
else puts("No Solution");
}
// fclose(stdin); fclose(stdout);
return 0;
}
写在最后
由于作者才疏学浅，关于 BSGS 只做过找到以上题目。如果您有关于 BSGS 的题目可以推荐给作者，私信评论均可，我将会在做出来之后作为补充，谢谢您的鼓励和支持！
\text{Thank you for your reading !}
本文参考李煜东《算法竞赛进阶指南》以及 OI Wiki 。