学习笔记——BSGS

众所周知，北上广深是中国非常一线的城市，北京是首都，地处……

正片开始！

一、BSGS基础算法

实现目标：$A^x\equiv B(\mathrm{mod}P),(\gcd (P,A)=1)$求最小的$x$
很明显，如果暴力枚举，时间是$O(P)$的，只要题目数据范围大，就死定了。愿意的人欢迎尝试（无100警告）
于是，考虑 ~  莫队
~~~~~~~~~~~~~~~~                 分块
~~~~~~~~~~~~~~~~                 BSGS
为什么我要提前两个？
因为BSGS本质就是分块！
简单讲解一下，就是将本来$P$种情况，平均分成了$\sqrt p $份，对每份内进行预处理
不直观？好，那就用直观的式子吧！
$$\text{令}x=k\sqrt{p}-t$$
$$\text{即}{A}^{k\sqrt{p}}\equiv A^{t}B(\mathrm{mod}p)$$

于是，找个哈希表维护一下后面的即可

IO::pin>>y>>z>>p;
gp_hash_table<int,int> ht;
int f,s;
bool flg;
ht.clear();
f=ceil(sqrt(p));
s=1;
flg=1;
for(int i=1; i<=f; i++)s=1ll*s*y%p,ht[1ll*z*s%p]=i;
for(int j=1,k=s; j<=f; j++) {if(ht[k]&&flg) {wt(((1ll*j*f-ht[k])%p+p)%p,'\n');flg=0;}k=(1ll*s*k)%p;}if(flg)puts("Orz, I cannot find x!");

附赠模板代码

#pragma GCC optimize(1,"inline","Ofast")
#pragma GCC optimize(2,"inline","Ofast")
#pragma GCC optimize(3,"inline","Ofast")
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
namespace IO {class input {private:bool isdigit(char c) {return ('0'<=c&&c<='9');}public:input operator>>(int &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(short &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(bool &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(long &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(long long &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(__int128 &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(unsigned int &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(unsigned short &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(unsigned long &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(unsigned long long &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(unsigned __int128 &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(!y)x=-x;return *this;}input operator>>(double &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=x*10+(c^48),c=getchar();if(!y)x=-x;if(!isdigit(c))if(c!='.')return *this;double z=1;while(isdigit(c))z/=10.,x=x+z*(c^48),getchar();return *this;}input operator>>(long double &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=x*10+(c^48),c=getchar();if(!y)x=-x;if(!isdigit(c))if(c!='.')return *this;double z=1;while(isdigit(c))z/=10.,x=x+z*(c^48),c=getchar();return *this;}input operator>>(float &x) {x=0;bool y=1;char c=getchar();while(!isdigit(c))y&=(c!='-'),c=getchar();while(isdigit(c))x=x*10+(c^48),c=getchar();if(!y)x=-x;if(!isdigit(c))if(c!='.')return *this;double z=1;while(isdigit(c))z/=10.,x=x+z*(c^48),c=getchar();return *this;}input operator>>(std::string &x) {char c=getchar();x.clear();while(!(c!=' '&&c!='\n'&&c!='	'&&c!=EOF&&c))c=getchar();while(c!=' '&&c!='\n'&&c!='	'&&c!=EOF&&c) {x.push_back(c);c=getchar();}return *this;}input operator>>(char *x) {char c=getchar();int cnt=0;while(!(c!=' '&&c!='\n'&&c!='	'&&c!=EOF&&c))c=getchar();while(c!=' '&&c!='\n'&&c!='	'&&c!=EOF&&c) {x[cnt++]=c;c=getchar();}return *this;}input operator>>(char x) {x=getchar();return *this;}} pin;
};
inline void wt(char ch) {putchar(ch);
}
template<class T>
inline void wt(T x) {static char ch[40];int p=0;if(x<0)putchar('-'),x=-x;doch[++p]=(x%10)^48,x/=10;while(x);while(p)putchar(ch[p--]);
}
template<class T,class... U>
inline void wt(T x,U ...t) {wt(x),wt(t...);
}
#define int long long
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define frep(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define lqrep(i,a,v) for(int i=hd[a],v=e[i].v;i>=i##end;i=e[i].nxt,v=e[i].v)
const int N=1e5+7;
main() {
}
//目前快速输出pout还未搞定哦

到此就结束了吗？

当然不是！！！！！！！！！！

如果没有$\gcd (P,A)=1$的话，前面的一切都成了一纸空文
那该如何？
如果不需要的旅客们可以摆烂了，以下是扩展板

二、BSGS基础算法

不妨设$\gcd (P,A)=d$
$$\begin{gathered} A^x\equiv B(\mathrm{mod}P)-> \\ (A^{\prime }\times d{)}^x\equiv B^{\prime }\times d(\mathrm{mod}P)-> \\ (A^{\prime }\times d{)}^{x-1}\equiv B^{\prime }\ast A^{\prime -1}(\mathrm{mod}P) \end{gathered}$$
接着按上文求解即可