P4454破解D-H协议

Problem

传送门

给定(g,P,A,B),其中(P)为质数

并且满足:

(g^a=A mod P)

(g^b=B mod P)

求(g^{a*b})

Solution

又是知道板子直接A系列……

用到了BSGS(大步小步法)……

还是介绍一下吧……

BSGS主要用来解决(A^xequiv B ( mod C))已知(A,B,C)(其中(C)为质数)求(x)。

具体实现其实还挺好理解的

令(D = A^sqrt {C})

通过枚举(i)我们有:

(D^i*A^{x_0}equiv B ( mod C))

有没有一种熟悉的感觉？

表示没有

由于(D^i,B,C)都是已知数，所以我们可以通过解同余方程得到一个解(X),然后判断(X)是否可表示为(A^{x_0})这种形式……

那么只需在预处理时用(map/hash)将(A^i,i∈[1,sqrt C])存下来即可。

对于这道题：

知道了BSGS的话直接粘板子，稍微改一下就可以A了……

上代码:

Code

#include <bits/stdc++.h>

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

inline int read(){
	int res = 0, fl = 1;
	char r = getchar();
	for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1;
	for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48;
	return res * fl;
}
typedef long long LL;
typedef pair<int, int> pii;
const int Maxn = 1e5;
map <int,short> Map;
int g[Maxn],G[Maxn], mod, n;
int Pow(int a, int b){
	int mul = 1;
	while(b){
		if(b & 1) mul = 1ll * mul * a % mod;
		a = 1ll * a * a % mod;
		b = b >> 1;
	}
	return mul;
}
void init(){
	n = sqrt(mod - 1) + 1, G[0] = g[0] = 1;
	for (int i = 1; i <= n; ++i) g[i + 1] = 1ll * g[i] * g[1] % mod;
   	for (int i = 0; i <= n; ++i) Map[g[i]] = i + 1;
	G[1] = g[n];
	for (int i = 1; i <= n; ++i) G[i + 1] = 1ll * G[i] * G[1] % mod;
}
int solve(int A){
	for (int i = 0; i <= n; ++i){
		int inv = Pow(G[i],mod - 2);
		int xz = 1ll * inv * A % mod;
		//printf("%d %d %d
",xz, Map[xz], i * n + Map[xz] - 1);
		if(Map[xz]) return i * n + Map[xz] - 1;
	}
	return 0;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
#endif
	g[1] = read(), mod = read();
	int Q = read();
	init();
	while(Q--){
		int x = solve(read());
		printf("%d
",Pow(read(), x));
	}
	return 0;
}