【题解】[CQOI2018]破解D-H协议

前言

人生中第一道紫题，写一篇题解纪念一下。

BSGS

BSGS（拔山盖世，北上广深 ）是什么呢？

它是一种能够在$O(\sqrt n\space)$的时间复杂度内求解类似于$a^x \equiv b \pmod{p}$的算法。

首先，我们设$x=i\sqrt p-j$，其中$i,j\in [0,\sqrt p\space]$

那么这个式子就变成了$a^{i\sqrt p-j} \equiv b\pmod p$

两边同时乘上$a^j$，很显然，等式变成了

$a^{i\sqrt p} \equiv ba^j\pmod p$

到了这一步，我们就可以先枚举$j$，每次把$ba^j\bmod p$存入哈希表。

然后再枚举$i$，在哈希表中查找$a^{i\sqrt p}$，如果找到了，就说明这个等式成立，$x$就应该是$i\sqrt p-j$，如果枚举完了也没找着，就说说明这个等式不成立。

在这个过程中，我们仅仅枚举了两次，时间复杂度只有区区的$O(\sqrt n\space)$

题目大意

看起来这个题目很复杂，但其实就是一个BSGS的模板。

简化一下题意，题目告诉你$g^a\bmod p$和 $g^b\bmod p$，让你求$g^{ab}\bmod p$。

观察一下，我们发现

$$g^{ab}\bmod p$$

$$=(g^a)^b\bmod p$$

$$=(g^a\bmod p)^b\bmod p$$

$$= A^b\bmod p$$

也就是说，只要我们把$b$求出来，那就万事大吉了。

那么如何求$b$呢？

观察发现：

$$B=g^b\bmod P$$

$$B \equiv g^b\pmod P$$

$$g^b \equiv B\pmod P$$

这不就是BSGS的模板吗？

我们可以用BSGS求出$b$，然后把用$b$求出$A^b\bmod p$。

有了这个思路，我们就可以开始写代码了！

注：这题很卡常，不要用cincout，记得开longlong，最后要开O2

AC代码（记得开O2）：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int g,n,p;//在最开始就定义三个全局变量
int qpow(int a,int b){
	//快速幂模板
	int res=1;
	while(b){
		if(b&1) res=(a*res)%p;
		a=(a*a)%p;
		b>>=1;
	}
	return res;
}
int BSGS(int b){
	map<int,int>m;//哈希表可以用map代替
	int t=ceil(sqrt(p));//记得要向上取整
	for(int i=1;i<=t;i++) m[b*qpow(g,i)%p]=i;//枚举j，存入哈希表中
	for(int i=1;i<=t;i++){
		int k=qpow(g,i*t)%p;
		if(m[k]) return i*t-m[k];//如果在哈希表中找到了这个值，就说明找到了b
	}
	return -1;//如果没有找到，就说明无解
}

signed main(){
	scanf("%lld%lld%lld",&g,&p,&n);
	for(int i=1;i<=n;i++){
		int A,B;
		scanf("%lld%lld",&A,&B);
		int b=BSGS(B);//用BSGS求出b
		printf("%lld\n",qpow(A,b)%p);//用快速幂求出K
	}
	return 0;
}