写在前面
在某次集训比赛时遇到了$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 117 |
#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 128 |
#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; } |