BSGS（模板）

用于解决A=g^a mod P中计算a

#include<cstdlib> #include<cstdio> #include<cmath> #include<cstring> #include<ctime> #include<iostream> #include<string> #include<vector> #include<list> #include<deque> #include<stack> #include<queue> #include<map> #include<set> #include<algorithm> //#pragma GCC optimize(2) using namespace std; typedef long long ll; const int INF=0x7fffffff; template<class T> inline T read(T&x){T data=0;int w=1;char ch=getchar();while(ch!='-'&&!isdigit(ch))ch=getchar();if(ch=='-')w=-1,ch=getchar();while(isdigit(ch))data=10*data+ch-'0',ch=getchar();return x=data*w; } ll g,p,bl,A,B; map <ll,ll> mp;int pow1(ll x,ll k){ll ans=1;while(k>0){if(k&1)ans=(ans*x)%p;x=(x*x)%p;k>>=1;}return ans; }void init() {bl=ceil(sqrt(p));ll cur=pow1(g,bl),ans=cur;mp[ans]=bl;for(ll i=2;i<=bl;++i){ans=(ans*cur)%p;mp[ans]=i*bl;} }ll BSGS(ll x) {ll j=0,cur=1;for(;j<=bl;++j){if(mp[(cur*A)%p])return mp[(cur*A)%p]-j;cur=(cur*g)%p;} }int main() {read(g);read(p);init();ll n;read(n);while(n--){read(A);//read(B);printf("%lld\n",BSGS(A));}return 0; }

 

转载于:https://www.cnblogs.com/xiaolaji/p/9439324.html

总结

以上是生活随笔为你收集整理的BSGS（模板）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。