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$ 。
$a,b$ 已知，对于所有 $j\in \lbrack 0, t)$ ，把 $b\times a^j \bmod p$ 丢进一个 Hash 表。
对于所有 $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 的实现。
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;
}
从小到大枚举，及时返回。
注意在算乘方的时候使用快速幂复杂度会非常假，从小到大顺便乘可以保证正确的复杂度。
第一问快速幂，第二问求个逆元，第三问 BSGS 。
这题不知道哪个毒瘤地方要开 long long 。
由于原根的性质，随便选一组求解然后快速幂即可。
给了一个递推式 $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
//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;
}
还是一个递推式 $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 。
本题保证有解。
题目只关心个位，于是转化为求 $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 。
拓展篇 exBSGS 恶心BSGS
咋啥东西都有 ex 。
SP3105 MOD - Power Modulo Inverted 题解
好耶，紫色的双倍经验！
普通的 BSGS 只能解决 $a$ 与 $p$ 互质的情况，而 exBSGS 不需要这个条件。
不互质咋办？变成互质！
方程两边同时除以 $\gcd(a,p)$ ，注意模数 $p$ 也要除，若 $\gcd(a,p) \nmid b$ 则无解。
若仍不互质则重复进行上述过程，直至 $p$ 与 $a$ 互质。
记 $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 。
