【概述】

BSGS（Baby?Step?Giant?Step）算法，又稱大小步算法，其主要用于解形如??的高次同余方程中的 x，其核心思想是分塊。

當 A?與 C?互質時，通過費馬小定理：

可知，當??時，會出現一個循環節，于是就能保證答案 x?若存在，必然有?

因此，當 C?比較小時，可使用暴力，直接令從 0 枚舉到 C-1，檢驗其是否為方程的解，而當 C?比較大時，使用暴力會 TLE，此時可以采用 BSGS 算法來求解 x，其時間復雜度是? 級別的

樸素的 BSGS 算法只能處理?C?是質數的情況，擴展的 BSGS 通過同余性質消因子來解決 C?不是質數的情況。

【BSGS 算法】

1.算法思想

根據分塊思想，設置一個變量?，此時使用 ceil() 函數向上取整，可以保證?，從而避免遺漏答案。

不難發現，此時 x?可表示為：

那么 ?就轉為?

移項，得：

此時對左邊的 j 從 0 枚舉到 size-1，將???加入 Hash 表中（這一步是 Baby Step）

再對右邊進行枚舉?（這一步是 Giant Step），然后再從?Hash 表中查找是否有這個值，若有的話，則得到一組 (i,j)，那么可得到正確解：

2.實現

struct HashMap{//哈希表static const int Hash=999917,maxn=46340;int num,link[Hash],son[maxn+5],next[maxn+5],w[maxn+5];int top,Stack[maxn+5];void clear(){//清空表num=0;while(top)link[Stack[top--]]=0;}void add(int x,int y){//添加鍵值元素son[++num]=y;next[num]=link[x];w[num]=INF;link[x]=num;}bool count(int y){//判斷表中是否有對應值int x=y%Hash;for(int j=link[x];j;j=next[j])if(y==son[j])return true;return false;}int &operator [](int y){//獲取鍵的對應值int x=y%Hash;for(int j=link[x];j;j=next[j])if(y==son[j])return w[j];add(x,y);Stack[++top]=x;return w[num];} }hashMap;int extendedGCD(int x,int y,int &a,int &b){if(y==0){a=1;b=0;return x;}int temp;int gcd=extendedGCD(y,x%y,a,b);temp=a;a=b;b=temp-x/y*b;return gcd; } int BSGS(int A,int B,int C){//三種特判if(C==1){if(!B)return A!=1;return -1;}if(B==1){if(A)return 0;return -1;}if(A%C==0){if(!B)return 1;return -1;}hashMap.clear();int Size=ceil(sqrt(C)),D=1,Base=1;for(int i=0;i<=Size-1;i++){//將A^j存進哈希表hashMap[Base]=min(hashMap[Base],i);//存儲最小的Base=((LL)Base*A)%C;}for(int i=0;i<=Size-1;i++){//擴展歐幾里得求A^jint x,y;int gcd=extendedGCD(D,C,x,y);//求出x、yx=((LL)x*B%C+C)%C;if(hashMap.count(x))//找到答案return i*Size+hashMap[x];D=((LL)D*Base)%C;}return -1;//無解 }int main(){int A,B,C;while(scanf("%d%d%d",&A,&B,&C)!=EOF&&(A+B+C)){int res=BSGS(A,B,C);if(res==-1)printf("No Solution\n");elseprintf("%d\n",res);}return 0; }

【擴展 BSGS 算法】

1.算法思想

對于 C 不是質數的情況，?等價于?

對其進行消因子處理，使得??化為??使得 C' 與 A?不再有可以約的因子：cnt=x-x'，每次消因子過程中，方程右邊同時消除一樣的因子

將??作為一個整體，利用擴展歐幾里得得到其解系，假設得到的一組原始特解為?，則：

化為高次同余方程：，此時可利用 BSGS 求解得到?，加回 cnt 即可得到原方程的解

需要注意的是，這樣得到的只有不大于 cnt 的解，可能會漏掉小于 cnt 的解，因此一般先從 1~log(50) 查找一遍

2.實現

struct HashMap{//哈希表static const int Hash=999917,maxn=46340;int num,link[Hash],son[maxn+5],next[maxn+5],w[maxn+5];int top,Stack[maxn+5];void clear(){//清空表num=0;while(top)link[Stack[top--]]=0;}void add(int x,int y){//添加鍵值元素son[++num]=y;next[num]=link[x];w[num]=INF;link[x]=num;}bool count(int y){//判斷表中是否有對應值int x=y%Hash;for(int j=link[x];j;j=next[j])if(y==son[j])return true;return false;}int &operator [](int y){//獲取鍵的對應值int x=y%Hash;for(int j=link[x];j;j=next[j])if(y==son[j])return w[j];add(x,y);Stack[++top]=x;return w[num];} }hashMap; int GCD(int a,int b){if(b==0)return a;return GCD(b,a%b); } int extendedGCD(int x,int y,int &a,int &b){if(y==0){a=1;b=0;return x;}int temp;int gcd=extendedGCD(y,x%y,a,b);temp=a;a=b;b=temp-x/y*b;return gcd; }int extendBSGS(int A,int B,int C){//三種特判if(C==1){if(!B)return A!=1;return -1;}if(B==1){if(A)return 0;return -1;}if(A%C==0){if(!B)return 1;return -1;}int gcd=GCD(A,C);int D=1,num=0;while(gcd!=1){//把A,C變成(A,C)=1為止if(B%gcd)return -1;B/=gcd;//從B中約去因子C/=gcd;//約C中約去因子D=((LL)D*A/gcd)%C;//將多出的乘給Dnum++;//統計約去次數gcd=GCD(A,C);}int now=1;for(int i=0;i<=num-1;i++){//枚舉0~num-1if(now==B)return i;now=((LL)now*A)%C;}hashMap.clear();int Size=ceil(sqrt(C)),Base=1;for(int i=0;i<=Size-1;i++){//將A^j存進哈希表hashMap[Base]=min(hashMap[Base],i);//存儲答案最小的Base=((LL)Base*A)%C;}for(int i=0;i<=Size-1;i++){//擴展歐幾里得求A^jint x,y;int gcd=extendedGCD(D,C,x,y);//求出x、yx=((LL)x*B%C+C)%C;if(hashMap.count(x))return i*Size+hashMap[x]+num;//加回numD=((LL)D*Base)%C;}return -1;//無解 }int main(){int A,B,C;while(scanf("%d%d%d",&A,&B,&C)!=EOF&&(A+B+C)){int res=extendBSGS(A,B,C);if(res==-1)printf("No Solution\n");elseprintf("%d\n",res);}return 0; }

【例題】

• Discrete Logging（POJ-2417）(樸素 BSGS)：點擊這里
• Clever Y（POJ-3243）(擴展?BSGS)：點擊這里

新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的数论 —— 高次同余方程与 BSGS 算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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