BZOJ 5296: [Cqoi2018]破解D-H协议(BSGS)

传送门

解题思路

　　\(BSGS\)裸题？？要求的是\(g^a =A (mod\) \(p)\)，设\(m\)为\(\sqrt p\)，那么可以设\(a=i*m-j\)，式子变成

　　$$ g^{i*m-j}=A\mod p$$

　　然后把\(j\)移过去，

　　$$g^{i*m}=A*gj\mod p$$

　　然后可以预处理枚举\(j\)的值用哈希存下来，每次直接\(O(m)\)询问，总的时间复杂度为\(O(T\sqrt p \log)\)

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#define int long longusing namespace std;
typedef long long LL;int g,MOD,T,A,B,a,b,m;
map<int,int> mp;inline int fast_pow(int x,int y){
int ret=1;
for(;y;y>>=1){
if(y&1) ret=1ll*ret*x%MOD;
x=1ll*x*x%MOD;
}
return ret;
}inline void prework(){
m=ceil(sqrt(MOD));
int base=fast_pow(g,m),now=1;
mp[now]=0;
for(int i=1;i<=m;i++){
now=1ll*now*base%MOD;
mp[now]=i;
}
}inline int BSGS(int x){
int now=x;
if(mp.count(now)) return mp[now]*m;
for(int i=1;i<=m;i++){
now=1ll*now*g%MOD;
if(mp.count(now)) return mp[now]*m-i;
}
}signed main(){
scanf("%lld%lld%lld",&g,&MOD,&T);
prework();
while(T--){
scanf("%lld%lld",&A,&B);
a=BSGS(A); b=BSGS(B);
 a=(a%(MOD-1)+MOD-1)%(MOD-1);
b=(b%(MOD-1)+MOD-1)%(MOD-1);
printf("%lld\n",fast_pow(g,1ll*a*b%(MOD-1)));
}
return 0;
}