题目地址：洛谷：【P2485】[SDOI2011]计算器 – 洛谷、BZOJ：Problem 2242. — [SDOI2011]计算器

题目描述

你被要求设计一个计算器完成以下三项任务：
1、给定y、z、p，计算y^z mod p 的值；
2、给定y、z、p，计算满足xy ≡z(mod p)的最小非负整数x；
3、给定y、z、p，计算满足y^x ≡z(mod p)的最小非负整数x。
为了拿到奖品，全力以赴吧！

输入输出格式

输入格式：
输入文件calc.in 包含多组数据。
第一行包含两个正整数T、K，分别表示数据组数和询问类型（对于一个测试点内的所有数据，询问类型相同）。
以下T 行每行包含三个正整数y、z、p，描述一个询问。

输出格式：
输出文件calc.out 包括T 行.
对于每个询问，输出一行答案。
对于询问类型2 和3，如果不存在满足条件的，则输出“Orz, I cannot find x!”。

输入输出样例

输入样例#1：

3 1
2 1 3
2 2 3
2 3 3

输出样例#1：

2
1
2

输入样例#2：

3 2
2 1 3
2 2 3
2 3 3

输出样例#2：

2
1
0

输入样例#3：

4 3
2 1 3
2 2 3
2 3 3
2 4 3

输出样例#3：

0
1
Orz, I cannot find x!
0

说明

【数据规模和约定】
对于100%的数据，1<=y,z,p<=10^9，为质数，1<=T<=10。

题解

$K=1$快速幂。
$K=2$时，考虑展开该式，$xy \equiv z \pmod{p} \Leftrightarrow xy + kp = z$，贝祖等式有解的条件是$\gcd(y, p)|z$，判一下有无解然后扩欧或费马小定理解决一下就好。
$K=3$时裸BSGS板，需要注意的是，要特判$y = 0$的情况。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cmath>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

inline LL fpow(LL n, LL k, LL p) {
    LL res = 1; n %= p;
    for(; k; k >>= 1) {
        if(k & 1) res = res * n % p;
        n = n * n % p;
    }
    return res;
}

inline LL gcd(LL a, LL b) {
    if(!b) return a;
    return gcd(b, a % b);
}

const int MO = 611977, MAXN = 1000005;

struct LinkedHashMap {
    int head[MO + 5], key[MAXN], val[MAXN], nxt[MAXN], tot;
    inline void clear() {
        tot = 0; memset(head, -1, sizeof(head));
    }
    LinkedHashMap() {
        clear();
    }
    inline void insert(int k, int v) {
        int idx = k % MO;
        for(int i = head[idx]; ~i; i = nxt[i]) {
            if(key[i] == k) {
                val[i] = v; return;
            }
        }
        key[tot] = k; val[tot] = v; nxt[tot] = head[idx]; head[idx] = tot++;
    }
    inline int operator[](const int &k) const {
        int idx = k % MO;
        for(int i = head[idx]; ~i; i = nxt[i]) {
            if(key[i] == k) return val[i];
        }
        return -1;
    }
} x;

inline LL bsgs(LL a, LL b, LL p) {
    a %= p; b %= p;
    if(a == 0) return b == 0 ? 1 : -1;
    if(b == 1) return 0;
    x.clear(); x.insert(1, 0);
    LL m = ceil(sqrt(p - 1)), inv = fpow(a, p - m - 1, p);
    for(LL i = 1, e = 1; i < m; i++) {
        e = e * a % p;
        if(x[e] == -1) x.insert(e, i);
    }
    for(LL i = 0; i < m; i++) {
        LL res = x[b];
        if(res != -1) return i * m + res;
        b = b * inv % p;
    }
    return -1;
}

int T, K;

int main() {
    T = readint(); K = readint();
    while(T--) {
        LL y = readint(), z = readint(), p = readint();
        if(K == 1) {
            printf("%lld\n", fpow(y, z, p));
        } else if(K == 2) {
            LL g = gcd(y, p);
            if(z % g) puts("Orz, I cannot find x!");
            else printf("%lld\n", fpow(y * fpow(z, p - 2, p) % p, p - 2, p));
        } else {
            LL res = bsgs(y, z, p);
            if(res == -1) puts("Orz, I cannot find x!");
            else printf("%lld\n", res);
        }
    }
    return 0;
}