bzoj2242 [SDOI2011]计算器

发表于

数论板题大杂烩，存个代码。
就是个板子。
好像在这里多写一点东西就不会出现之前的问题了。
应该吧。

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
#include <cstdio>
#include <map>
#include <cmath>
 
int FastPow(int a, int b, int p) {
    int res = 1;
    for(; b; b >>= 1, a = 1LL * a * a % p) 
        if(b & 1) res = 1LL * res * a % p;
    return res;
}
 
int exgcd(int a, int b, int &x, int &y) {
    if(b == 0) {
        x = 1, y = 0;
        return a;
    }
    int r = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return r;
}
 
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
 
int Get(int y, int z, int p) {
    int r = gcd(y, p), res;
    if(z % r != 0) return -1;
    z /= r, y /= r, p /= r;
    exgcd(y, p, res, r);
    return (1LL * res * z % p + p) % p;
}
 
int bsgs(int y, int z, int p) {
    std::map<int, int> map;
    int m = ceil(sqrt(p)), tmp = FastPow(y, p - m - 1, p);
    y = y % p;
    if(y == 0 && z == 0) return 1;
    if(y == 0) return -1;
    for(int k = 1, i = 0; i < m; i++, k = 1LL * k * y % p)
        if(!map.count(k)) map[k] = i;
    for(int k = z % p, i = 0; i < m; i++, k = 1LL * k * tmp % p)
        if(map.count(k)) return i * m + map[k];
    return -1;
}
 
int main(int argc, char *argv[]) {
    int t, k;
    scanf("%d%d", &t, &k);
    while(t--) {
        int y, z, p;
        scanf("%d%d%d", &y, &z, &p);
        if(k == 1) printf("%d\n", FastPow(y, z, p));
        else if(k == 2) {
            int r = Get(y, z, p);
            if(r == -1) puts("Orz, I cannot find x!");
            else printf("%d\n", r);
        } else {
            int r = bsgs(y, z, p);
            if(r == -1) puts("Orz, I cannot find x!");
            else printf("%d\n", r);
        }
    }
    return 0;
}