BSGS&exBSGS 学习笔记
BSGS&exBSGS 学习笔记
写在前面
在某次集训比赛时遇到了esBSGS毒瘤题，被大佬们暴捶，过了一个多月本蒟蒻才开始学习BSGS\text{&}exBSGS
BSGS
BabyStepGiantStep算法，即大步小步算法，缩写为BSGS，而esBSGS，顾名思义，就是BSGS的拓展。 BSGS用来解决如下问题： 给定一个质数P(2\leq P < 2^{31})Y(2\leq A < P)Z(2\leq Z <P)X，满足Y^X \equiv Z \mod P 例题：Luogu P3846 [TJOI2007]可爱的质数 算法思路如下： 设m=\sqrt{P}，X=a\times m-b，a\in [0,m+1]，n \in [0,m)。 那么Y^{a \times m-b}\equiv Z \mod P Y^{a\times m}\equiv Z \times Y^{b} \mod P， 所以只要O(m)记录一下右边的值，然后枚举左边，查表即可。
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;
#define re register
#define int long long
class Quick_Input_Output{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Rd)+fread(Rd,1,S,stdin),A==B)?EOF:*A++)
char Rd[S],*A,*B;
#define pc putchar
public:
#undef gc
#define gc getchar
inline int read(){
int res=0,f=1;char ch=gc();
while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=gc();}
while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=gc();
return res*f;
}
inline void write(int x){
if(x<0) pc('-'),x=-x;
if(x<10) pc(x+'0');
else write(x/10),pc(x%10+'0');
}
#undef gc
#undef pc
}I;
#define File freopen("%name%.in","r",stdin);freopen("%name%.out","w",stdout);
int p,y,z,m,ans;
map<int,int> mp;
int fpow(int a,int b){
int s=1;
while(b){
if(b&1) s*=a,s%=p;
a*=a;
a%=p;
b>>=1;
}
return s;
}
int calc(int x){
int s=z;
s*=fpow(y,x);s%=p;
return s;
}
signed main(){
// File
p=I.read();y=I.read();z=I.read();
if(y==1) return puts("0"),0;
m=sqrt(p)+1;
mp.clear();
for(int pw=z,i=0;i<m;i++){
mp[pw]=i;
pw*=y;pw%=p;
}
ans=-1;
for(int s=1,pw=fpow(y,m),i=1;i<=m+1;i++){
s*=pw;s%=p;
if(mp.count(s)){
ans=i*m-mp[s];
break;
}
}
if(ans==-1) return puts("no solution"),0;
I.write(ans);putchar('\n');
return 0;
}exBSGS
exBSGS顾名思义（大雾），就是BSGS的拓展。适用于解决如下问题： 给定一个整数P(2\leq P < 2^{31})Y(2\leq A < P)Z(2\leq Z <P)X，满足Y^X \equiv Z \mod P 例题：Luogu P4195 【模板】exBSGS/Spoj3105 Mod 算法思路如下： 对于gcd(y, p)\ne1怎么办？ 我们把它写成y\times y^{x-1}+k\times p=z, k\in Z的形式 根据exgcd的理论 那么如果gcd(y,p)不是z的约数就不会有解 设d=gcd(y,p) 那么\frac{y}{d}\times y^{x-1}+k\times \frac{p}{d}=\frac{z}{d} 递归到d=1 设之间的所有的d乘积为g，递归c次 令x’=x-c, p’=\frac{p}{g},z’=\frac{z}{g} 那么y^{x’}\times \frac{y^c}{g}=z’(mod \ p’) 那么BSGS求解就好了
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<unordered_map>
using namespace std;
#define re register
#define int long long
class Quick_Input_Output{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Rd)+fread(Rd,1,S,stdin),A==B)?EOF:*A++)
char Rd[S],*A,*B;
#define pc putchar
public:
#undef gc
#define gc getchar
inline int read(){
int res=0,f=1;char ch=gc();
while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=gc();}
while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=gc();
return res*f;
}
inline void write(int x){
if(x<0) pc('-'),x=-x;
if(x<10) pc(x+'0');
else write(x/10),pc(x%10+'0');
}
#undef gc
#undef pc
}I;
#define File freopen("%name%.in","r",stdin);freopen("%name%.out","w",stdout);
int p,y,z,m,ans;
std::unordered_map<int,int> Hash;
int fpow(int a,int b){
int s=1;a%=p;
while(b){
if(b&1) s*=a,s%=p;
a*=a;
a%=p;
b>>=1;
}
return s;
}
int gcd(int a,int b){
return !b?a:gcd(b,a%b);
}
int EX_BSGS(){
y%=p;z%=p;
if(y==1) return puts("0"),0;
Hash.clear();
re int cnt=0,t=1;
for(int d=gcd(y,p);d!=1;d=gcd(y,p)){
if(z%d) return puts("No Solution"),0;
++cnt,z/=d,p/=d,t=1ll*t*y/d%p;
if(z==t) return I.write(cnt),putchar('\n'),0;
}
m=sqrt(p)+1;
for(int pw=z,i=0;i<m;i++){
Hash[pw]=i;
pw*=y;pw%=p;
}
ans=-1;
for(int s=t,pw=fpow(y,m),i=1;i<=m;i++){
s*=pw;s%=p;
if(Hash.find(s)!=Hash.end()){
ans=i*m-Hash[s]+cnt;
break;
}
}
if(ans==-1) return puts("No Solution"),0;
I.write(ans);putchar('\n');
}
signed main(){
// File
while(1){
y=I.read();p=I.read();z=I.read();
if(p==0&&y==0&&z==0) return 0;
EX_BSGS();
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-09-20
，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录