BSGS&exBSGS 学习笔记

(Updated: )
oi
,

写在前面

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

BSGS

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#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%10+'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(2\leq P < 2^{31})$，以及一个整数$Y(2\leq A < P)$，一个整数$Z(2\leq Z <P)$，求最小的$X$，满足$Y^X \equiv Z \mod P$ 例题：Luogu P4195 【模板】exBSGS/Spoj3105 Mod 算法思路如下： 对于$gcd(y, p)\ne1$怎么办？ 我们把它写成$y\times y^{x-1}+k\times p=z, k\in Z$的形式 根据$exgcd$的理论 那么如果$gcd(y,p)$不是$z$的约数就不会有解 设$d=gcd(y,p)$ 那么$\frac{y}{d}\times y^{x-1}+k\times \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$求解就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#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%10+'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;
}