BSGS算法（Baby Steps Giant Steps算法，大步小步算法，北上廣深算法，拔山蓋世算法）

適用問題

對于式子：

$$x^y=z(mod_p)$$

已知x，z，p，p為質數(shù)；

求解一個最小非負整數(shù)y；

---

---

存在一個y,屬于[0,p-2]（費馬小定理）

于是有了一個笨拙的方法，枚舉y

枚舉y，期望效率：O(P)

尋求一種優(yōu)化：

對式子變型：

設：$$y=i\sqrt{p}-j$$

則$$x^{i\sqrt{p}-j}=z(mod_p)$$

——這個變型的用意在于把y拆開

枚舉y，變成枚舉，i,j；

i在1~$\sqrt{p}$之間，j在0~$\sqrt{p}$之間

（根號上取整，其實i，j的范圍大可大些——只要保證y不會小于0）

枚舉（i,j），期望效率：$O(\sqrt{p}*\sqrt{}p)$

本質上沒有優(yōu)化

接著變型：

$$x^{i\sqrt{p}}=z*x^{j}(mod_p)$$　

——這個變型的用意在于真正把y分離為兩部分

枚舉j，把等號右邊的模后得數(shù)置于hash_table,此時同一個得數(shù)只留最大的j值;

從小到大枚舉i，計算等號左邊的模后得數(shù)，查詢hash_table，第一個成功查詢的i，與其相應的j，組成$i\sqrt{p}-j$即為最小的y，

期望效率：$O(\sqrt{p}*T(hash))$

效率優(yōu)異，拔山蓋世的bsgs算法，就是這樣了；

---

---

?

例題：

[SDOI2011]計算器

代碼：

#include<cstring> #include<cstdio> #include<cmath> #define LL long long const int ss=999983; using namespace std; int hash_tab[1000000],tot; struct ss{int nu,next,j; }data[1000000]; void work(); void work1(); void work2(); void work3(); LL Sqr(LL ,int ); int hash(int, int ,int ); LL z,y,p; bool flag; int main() {work(); } void work(){int T,K;scanf("%d%d",&T,&K);while(T--){scanf("%lld%lld%lld",&y,&z,&p);if(K==1)work1();if(K==2)work2();if(K==3)work3();} } void work1(){int i,j,k;printf("%lld\n",Sqr(y,z)); } void work2(){int ans,less;if((!(y%p)&&z)||((y%p)&&!z)){printf("Orz, I cannot find x!\n");return;}printf("%lld\n",Sqr(y%p,p-2)*z%p); } void work3(){long long ysqrtp,sqrtp=ceil(sqrt(p));memset(hash_tab,0,sizeof(hash_tab));memset(data,0,sizeof(data));long long l=1,r=z%p;int i,j;if((!(y%p)&&z)||((y%p)&&!z)){printf("Orz, I cannot find x!\n");return;}ysqrtp=Sqr(y,sqrtp);for(i=0;i<=sqrtp;i++)hash(r,i,0),(r*=y)%=p;for(i=1;i<=sqrtp;i++){(l*=ysqrtp)%=p;if((j=hash(l,0,1))!=-1){printf("%lld\n",i*sqrtp-j);return ;}}printf("Orz, I cannot find x!\n"); } LL Sqr(LL x,int n){LL ret=1;while(n){if(n&1)(ret*=x)%=p;(x*=x)%=p;n>>=1;}return ret; } int hash(int num,int j,int flag){int tem;for(tem=hash_tab[num%ss];tem;tem=data[tem].next){if(data[tem].nu==num){if(!flag&&j>data[tem].j)data[tem].j=j;return data[tem].j;}if(!data[tem].next&&!flag){data[tem].next=++tot;data[tot].j=j;data[tot].nu=num;return -1;}}if(!flag){hash_tab[num%ss]=++tot;data[tot].j=j;data[tot].nu=num;}return -1; } View Code

?

轉載于:https://www.cnblogs.com/nietzsche-oier/p/7493671.html

總結

以上是生活随笔為你收集整理的bsgs(Baby Steps Giant Steps)算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。