BSGS&exBSGS 学习笔记

2022-09-19 11:33:18 浏览数 (3)

BSGS&exBSGS 学习笔记

写在前面

在某次集训比赛时遇到了esBSGS毒瘤题，被大佬们暴捶，过了一个多月本蒟蒻才开始学习BSGStext{&}exBSGS

BSGS

BabyStepGiantStep算法，即大步小步算法，缩写为BSGS，而esBSGS，顾名思义，就是BSGS的拓展。 BSGS用来解决如下问题： 给定一个质数P(2leq P < 2^{31})Y(2leq A < P)Z(2leq Z <P)X，满足Y^X equiv Z mod P 例题：Luogu P3846 [TJOI2007]可爱的质数 算法思路如下： 设m=sqrt{P}，X=atimes m-b，ain [0,m 1]，n in [0,m)。 那么Y^{a times m-b}equiv Z mod P Y^{atimes m}equiv Z times Y^{b} mod P， 所以只要O(m)记录一下右边的值，然后枚举左边，查表即可。

代码语言：javascript复制
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;

#define re register
#define int long long 

class Quick_Input_Output{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Rd) fread(Rd,1,S,stdin),A==B)?EOF:*A  )
        char Rd[S],*A,*B;
        #define pc putchar
    public:
        #undef gc
        #define gc getchar 
        inline int read(){
            int res=0,f=1;char ch=gc();
            while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=gc();}
            while(ch>='0'&&ch<='9') res=res*10 ch-'0',ch=gc();
            return res*f;
        }
        inline void write(int x){
            if(x<0) pc('-'),x=-x;
            if(x<10) pc(x '0');
            else write(x/10),pc(x '0');
        }
        #undef gc
        #undef pc
}I;
#define File freopen("%name%.in","r",stdin);freopen("%name%.out","w",stdout);

int p,y,z,m,ans;
map<int,int> mp;
int fpow(int a,int b){
    int s=1;
    while(b){
        if(b&1) s*=a,s%=p;
        a*=a;
        a%=p;
        b>>=1;
    }
    return s;
}
int calc(int x){
    int s=z;
    s*=fpow(y,x);s%=p;
    return s; 
}
signed main(){
//  File
    p=I.read();y=I.read();z=I.read();
    if(y==1) return puts("0"),0;
    m=sqrt(p) 1;
    mp.clear();
    for(int pw=z,i=0;i<m;i  ){
        mp[pw]=i;
        pw*=y;pw%=p;
    }
    ans=-1;
    for(int s=1,pw=fpow(y,m),i=1;i<=m 1;i  ){
        s*=pw;s%=p;
        if(mp.count(s)){
            ans=i*m-mp[s];
            break;
        }
    }
    if(ans==-1) return puts("no solution"),0;
    I.write(ans);putchar('n');
    return 0;
}

exBSGS

exBSGS顾名思义（大雾），就是BSGS的拓展。适用于解决如下问题： 给定一个整数P(2leq P < 2^{31})Y(2leq A < P)Z(2leq Z <P)X，满足Y^X equiv Z mod P 例题：Luogu P4195 【模板】exBSGS/Spoj3105 Mod 算法思路如下： 对于gcd(y, p)ne1怎么办？ 我们把它写成ytimes y^{x-1} ktimes p=z, kin Z的形式 根据exgcd的理论 那么如果gcd(y,p)不是z的约数就不会有解 设d=gcd(y,p) 那么frac{y}{d}times y^{x-1} ktimes frac{p}{d}=frac{z}{d} 递归到d=1 设之间的所有的d乘积为g，递归c次 令x’=x-c, p’=frac{p}{g},z’=frac{z}{g} 那么y^{x’}times frac{y^c}{g}=z’(mod p’) 那么BSGS求解就好了

代码语言：javascript复制
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<unordered_map>
using namespace std;

#define re register
#define int long long 

class Quick_Input_Output{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Rd) fread(Rd,1,S,stdin),A==B)?EOF:*A  )
        char Rd[S],*A,*B;
        #define pc putchar
    public:
        #undef gc
        #define gc getchar 
        inline int read(){
            int res=0,f=1;char ch=gc();
            while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=gc();}
            while(ch>='0'&&ch<='9') res=res*10 ch-'0',ch=gc();
            return res*f;
        }
        inline void write(int x){
            if(x<0) pc('-'),x=-x;
            if(x<10) pc(x '0');
            else write(x/10),pc(x '0');
        }
        #undef gc
        #undef pc
}I;
#define File freopen("%name%.in","r",stdin);freopen("%name%.out","w",stdout);
int p,y,z,m,ans;
std::unordered_map<int,int> Hash;
int fpow(int a,int b){
    int s=1;a%=p;
    while(b){
        if(b&1) s*=a,s%=p;
        a*=a;
        a%=p;
        b>>=1;
    }
    return s;
}
int gcd(int a,int b){
    return !b?a:gcd(b,a%b);
}
int EX_BSGS(){
    y%=p;z%=p;
    if(y==1) return puts("0"),0;
    Hash.clear(); 
    re int cnt=0,t=1; 
    for(int d=gcd(y,p);d!=1;d=gcd(y,p)){
        if(z%d) return puts("No Solution"),0;
          cnt,z/=d,p/=d,t=1ll*t*y/d%p;
        if(z==t) return I.write(cnt),putchar('n'),0;
    }
    m=sqrt(p) 1;
    for(int pw=z,i=0;i<m;i  ){
        Hash[pw]=i;
        pw*=y;pw%=p;
    }
    ans=-1;
    for(int s=t,pw=fpow(y,m),i=1;i<=m;i  ){
        s*=pw;s%=p;
        if(Hash.find(s)!=Hash.end()){
            ans=i*m-Hash[s] cnt;
            break;
        }
    }
    if(ans==-1) return puts("No Solution"),0;
    I.write(ans);putchar('n');
}
signed main(){
//  File
    while(1){
        y=I.read();p=I.read();z=I.read();
        if(p==0&&y==0&&z==0) return 0;
        EX_BSGS();
    }
    return 0;
}
海外加速 编程算法

0 人点赞