「BZOJ-2242」[SDOI2011]计算器 (BSGS)

发表于 | 分类于 ，

BZOJ2242 - [SDOI2011]计算器

题意

给定三个数$y,z,p$，进行如下三种操作：

1.计算Y^Z Mod P 的值
2.计算满足xy≡ Z ( mod P )的最小非负整数
3.计算满足Y^x ≡ Z ( mod P)的最小非负整数

题解

虽然我确实在找板题，但这种纯板题为什么会出现在OI省选……

op1：快速幂

op2：exgcd

op3：BSGS

都套板子就vansˊ_>ˋ

代码

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
65
66
67
68
69
#include <bits/stdc++.h>

using namespace std;

int qp(int a, int n, int mod)
{
	long long ans = 1, base = a;
	while(n)
	{
		if(n & 1) (ans *= base) %= mod;
		(base *= base) %= mod;
		n >>= 1;
	}
	return ans;
}

void exgcd(int a, int b, int &x, int &y)
{
    if(b == 0) { x = 1; y = 0; return; }
    exgcd(b, a % b, x, y);
    int t = x; x = y, y = t - a / b * y;
}

int BSGS(int a, int b, int p)
{
	map<int, int> hash;
	b %= p;
	int t = (int)sqrt(p) + 1;
	for(int j =0; j < t; j ++)
	{
		int val = 1ll * b * qp(a, j, p) % p;
		hash[val] = j;
	}
	a = qp(a, t, p);
	if(a == 0) return b == 0 ? 1 : -1;
	for(int i = 0; i <= t; i ++)
	{
		int val = qp(a, i, p);
		int j = hash.find(val) == hash.end() ? -1 : hash[val];
		if(j >= 0 && i * t - j >= 0) return i * t - j;
	}
	return -1;
}

int main()
{
    int t, k, y, z, p;
    scanf("%d%d", &t, &k);
    while(t --)
    {
        scanf("%d%d%d", &y, &z, &p);
        if(k == 1) printf("%d\n", qp(y, z, p));
        else if(k == 2)
        {
            int x, xx;
            exgcd(y, p, x, xx);
            x = 1ll * x * z % p;
            if(x) printf("%d\n", (x % p + p) % p);
            else puts("Orz, I cannot find x!");
        }
        else if(k == 3)
        {
            int ans = BSGS(y, z, p);
            if(~ans) printf("%d\n", ans);
            else puts("Orz, I cannot find x!");
        }
    }
    return 0;
}