[SDOI 2011] 计算器

题目大意

你被要求设计一个计算器完成以下三项任务:

1、给定 yyzzpp,计算 yzmodpy^z \bmod p 的值;

2、给定 yyzzpp,计算满足 xyz(modp)xy \equiv z (\bmod p) 的最小非负整数;

3、给定 yyzzpp,计算满足 yxz(modp)y^x \equiv z (\bmod p) 的最小非负整数。

无解时输出 Orz, I cannot find x!

多组询问,同一个点的任务相同。

1T101 \leqslant T \leqslant 10

1y, z, p1,000,000,000, p  1 \leqslant y, \ z, \ p \leqslant 1,000,000,000, \ p\; 为质数

题目链接

【SDOI 2011】计算器 - Luogu 2485

题解

第一个任务直接快速幂。

第二个任务,当且仅当 y0(modp),  z≢0(modp)y \equiv 0 (\bmod p), \; z \not\equiv 0 (\bmod p) 时无解;有解时,计算逆元后直接算就行。

第三个任务,用 BSGS 求。

代码

这类题还是都用 long long 比较省心啊。。。

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
#include <cstdio>
#include <cmath>
#include <map>
long long pow(long long a, long long n, long long p) {
long long res = 1;
for (; n; n >>= 1, a = a * a % p) if (n & 1) res = res * a % p;
return res;
}
namespace Quest1 {
void solve(long long a, long long b, long long p) {
printf("%lld\n", pow(a, b, p));
}
}
void exgcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) x = 1, y = 0;
else exgcd(b, a % b, y, x), y -= x * (a / b);
}
long long inv(long long a, long long p) {
long long res, temp;
exgcd(a, p, res, temp);
return (res % p + p) % p;
}
namespace Quest2 {
void solve(long long a, long long b, long long p) {
if (b % p != 0 && a % p == 0) puts("Orz, I cannot find x!");
else {
long long t = inv(a, p);
printf("%lld\n", b * t % p);
}
}
}
namespace Quest3 {
long long bsgs(long long a, long long b, long long p) {
a %= p, b %= p;
if (a == 0) return b == 0 ? 1 : -1;
std::map<long long, long long> map;
long long m = ceil(sqrt(p)), t = 1;
for (int i = 0; i < m; i++) {
if (!map.count(t)) map[t] = i;
t = t * a % p;
}
long long k = inv(t, p), w = b;
for (int i = 0; i < m; i++) {
if (map.count(w)) return i * m + map[w];
w = w * k % p;
}
return -1;
}
void solve(long long a, long long b, long long p) {
long long ans = bsgs(a, b, p);
if (ans == -1) puts("Orz, I cannot find x!");
else printf("%lld\n", ans);
}
}
int main() {
int T, k;
scanf("%d %d", &T, &k);
while (T--) {
long long y, z, p;
scanf("%lld %lld %lld", &y, &z, &p);
if (k == 1) Quest1::solve(y, z, p);
else if (k == 2) Quest2::solve(y, z, p);
else Quest3::solve(y, z, p);
}
return 0;
}