P4454破解D-H协议

Posted on |

Problem

传送门

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

并且满足:

$g^a=A\ \ mod\ \ P$

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

求$g^{a*b}$

Solution

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

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

还是介绍一下吧……

BSGS主要用来解决$A^x\equiv 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#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\n",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\n",Pow(read(), x));
	}
	return 0;
}