[学习笔记]BSGS

标签：include int 笔记 times 学习 pmod ch equiv BSGS

$\operatorname{BSGS}$ ，也即 $Baby\; step\; Giant\; step$ 大步小步算法，可以在 $\Theta(\sqrt{p})$ 的时间内求解

$$a^x\equiv b\pmod{p}$$

的问题，其中 $a,p$ 互质（也即 $a\perp p$）

那么首先显然地，$a^0\equiv 1\pmod{p}$；

又根据欧拉定理， $a^{φ(p)}\equiv 1\pmod{p}$

不难看出， $0\sim φ(p)$ 是一个循环节

也就是说，最多循环 $φ(p)$ 次就可以找到答案，否则无解

不妨设 $x=i\times m-k$，其中 $k\in [0,m]$

原方程变为 $a^{i\times m-k}\equiv b\pmod{p}$

移项，$a^{i\times m}\equiv a^kb\pmod{p}$

可以先计算 $a^kb\pmod{p}$ 的值，存入哈希表/ $\operatorname{map}$ 中

然后枚举可能的 $i$ 值，计算 $a^{i\times m}$ 的值进行查询

也就是说，$\operatorname{BSGS}$ 算法共分为两步：

$\qquad\mathfrak{1:}$ $[0,m]$ 枚举 $k$，将 $a^kb\mod p$ 的值存入哈希表中

$\qquad\mathfrak{2:}$ $[1,\left \lceil \frac{p}{m} \right \rceil]$ 枚举 $i$，将 $a^{i\times m}\mod p$ 在表中进行查询，如果存在，此时的 $i\times m-k$ 即为答案

模板题目：TJOI2007可爱的质数

 

 

#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#define WR WinterRain
#define int long long
using namespace std;
const int WR=5010,INF=1099588621776;
int BL,ans;
map<int,int>mp;
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<1)+(s<<3)+ch-48;
        ch=getchar();
    }
    return s*w;
}
int quick_pow(int a,int b,int mod){
    int base=a,res=1;
    while(b){
        if(b&1) res=res*base%mod;
        base=base*base%mod;
        b>>=1;
    }
    return res;
}
void baby_step(int a,int b,int p){
    int pw=0;
    while(pw<BL){
        if(!mp[b]) mp[b]=pw+1;
        b=b*a%p,pw++;
    }
}
void giant_step(int a,int b,int p){
    int pw=1,base,rec;
    base=rec=quick_pow(a,BL,p);
    while(pw<=BL){
        if(mp[base]) ans=min(ans,BL*pw-mp[base]+1);
        base=base*rec%p,pw++;
    }
}
signed main(){
    int p=read(),a=read(),b=read();
    BL=ceil(sqrt(p));ans=INF;
    // printf("%lld\n",BL);
    baby_step(a,b,p);
    giant_step(a,b,p);
    if(ans==INF) printf("no solution\n");
    else printf("%lld\n",ans);
    return 0;
}

View Code

 

 

 

$φ$

标签：include,int,笔记,times,学习,pmod,ch,equiv,BSGS
From： https://www.cnblogs.com/WintersRain/p/16564635.html