自动搬运

查看原文

来自洛谷，原作者为

	Leonid 我要逃离这里

搬运于2025-08-24 22:00:20，当前版本为作者最后更新于2021-08-02 14:12:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P4454 [CQOI2018]破解 D-H 协议 题解

不要看这道题题目长而且是紫题就放弃，只要读懂题目就不难了。

题目大意

给定质数 $P$，和模 $P$ 意义下的数 $g$，和一个正整数 $n$。

接下来给出 $n$ 组数据 每组数据一行两个整数 $A$ 和 $B$，其中 $A=g^a\ mod\ P$，$B=g^b\ mod\ P$，求 $g^{ab}\ mod\ P$ 的值。

这是一道的求高次同余方程的题，看似是要求两个方程，其实思考一下就可以发现只要算出一个方程就可以了。因为两条式子获得的是一样的 $K$，所以我们只需要用 BSGS 算法求其中一个方程的解，然后用快速幂输出就可以了。

BSGS 模板题

My code

#include<cstdio>
#include<cmath>
#include<map>

using namespace std;

#define ll long long //好习惯

ll g,p,n,A,B,qwq; //qwq表示其中一个方程的解
map<ll,ll>k; //hash表

ll qpow(ll a,ll b,ll p){
   ll e=1;
   while(b){
   	if(b&1)e=e*a%p;
   	b>>=1;
   	a=a*a%p;
   }
   return e%p;
} //快速幂模板

ll BSGS(ll a,ll b,ll p){
   k.clear(); //hash表初始化
   ll m=ceil(sqrt(p)),ans;
   for(ll i=0;i<=m;i++){
   	if(!i){
   		ans=b%p;
   		k[ans]=i;
   		continue;
   	}
   	ans=(ans*a)%p;
   	k[ans]=i;
   }
   ll t=qpow(a,m,p);
   ans=1;
   for(ll i=1;i<=m;i++){
   	ans=(ans*t)%p;
   	if(k[ans]){
   		ll o=i*m-k[ans];
   		return (o%p+p)%p; //返回答案
   	}
   }
   return -1;
} // BSGS模板

int main(){
   scanf("%lld %lld",&g,&p);
   scanf("%lld",&n);
   while(n--){
   	scanf("%lld %lld",&A,&B);
   	qwq=BSGS(g,A,p);
   	printf("%lld\n",qpow(B,qwq,p)); // 输出答案
   }
   return 0;
}