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 long

using 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;

}

巴特西

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

解题思路

代码

最新文章

热门文章