【BZOJ5296】【CQOI2018】破解D-H协议（BSGS）

传送门

题意：给定$g^a\%p,g^b\%p,求g^{(a*b)}\%p$

$CQOI$日常板子

$bsgs$求出$a,b$后代入即可
复杂度$O(nlogp)$

也可以先预处理再直接查找
会快很多

#include<bits/stdc++.h>
#include<tr1/unordered_map>
using namespace std;
using namespace tr1;
#define ll long long
#define int long long
inline int read(){
	char ch=getchar();
	int res=0,f=1;
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
	return res*f;
}
int n;
unordered_map<ll,ll>mp;
inline ll ksm(ll a,ll b,ll p,ll res=1){
	for(;b;a=a*a%p,b>>=1)res=res*((b&1)?a:1)%p;
	return res;
}
inline ll bsgs(int k,int n,int mod){
	mp.clear();
	int res=1;
 	int M=sqrt(mod)+1;
	for(int i=0;i<=M;i++){
		mp[n*res%mod]=i;
		res=res*k%mod;
	}
	int ans=-1;
	for(int i=1;i<=M;i++){
		int tmp=ksm(k,i*M,mod);
		if(mp[tmp]){return i*M-mp[tmp];}
	}
}
ll g,p,a,b,A,B;
signed main(){
	g=read(),p=read();
	n=read();
	for(int i=1;i<=n;i++){
		A=read(),B=read();
		a=bsgs(g,A,p),b=bsgs(g,B,p);
		cout<<ksm(g,a*b,p)<<'
';
	}
}