### 思路

本題是一個比較模板化的題目。

#### 一操作

考慮使用快速冪。

快速冪，只需要把 $k$ 變成二進制即可實現 $\Theta(\log k)$ 的時間復雜度。

實現方法：

```cpp
long long qmi(long long a,long long k,long long p){
?? ?long long res = 1;
?? ?while (k){
?? ??? ?if (k & 1){
?? ??? ??? ?res = (res * a) % p;
?? ??? ?}
?? ??? ?a = (a * a) %p;
?? ??? ?k >>= 1;
?? ?}
?? ?return res;
}
```

### 二操作

考慮使用乘法逆元，除一個數等于乘上那個數的逆元，當 $p$ 為質數時，$x$ 的逆元為 $x^{p-2}$。

計算 $x^{p-2}$ 也可以使用快速冪。

### 三操作

考慮使用 BSGS 算法來進行計算，具體實現代碼如下：

```cpp
long long bsgs(long long a,long long b,long long p){
?? ?unordered_map<long long,long long>mp;
?? ?if (1 % p == b % p){
?? ??? ?return 0;
?? ?}
?? ?long long k = sqrt(p) + 1;
?? ?for (long long i = 0,j = b % p; i < k; i ++ ){
?? ??? ?mp[j] = i;
?? ??? ?j = (long long)j * a % p;
?? ?}
?? ?long long t = 1 % p;
?? ?for (long long i = 0; i < k; i ++ ){
?? ??? ?t = (long long)t * a % p;
?? ?}
?? ?for (long long i = 1,j = t; i <= k; i ++ ){
?? ??? ?if (mp.count(j)){
?? ??? ??? ?return (long long)i * k - mp[j];
?? ??? ?}
?? ??? ?j = (long long)j * t % p;
?? ?}
?? ?return -1;
}
```

### 最終代碼

只需要把給出的那些東西合并起來即可。

```cpp
#include <bits/stdc++.h>
using namespace std;
long long qmi(long long a,long long k,long long p){
?? ?long long res = 1;
?? ?while (k){
?? ??? ?if (k & 1){
?? ??? ??? ?res = (res * a) % p;
?? ??? ?}
?? ??? ?a = (a * a) %p;
?? ??? ?k >>= 1;
?? ?}
?? ?return res;
}
long long bsgs(long long a,long long b,long long p){
?? ?unordered_map<long long,long long>mp;
?? ?if (1 % p == b % p){
?? ??? ?return 0;
?? ?}
?? ?long long k = sqrt(p) + 1;
?? ?for (long long i = 0,j = b % p; i < k; i ++ ){
?? ??? ?mp[j] = i;
?? ??? ?j = (long long)j * a % p;
?? ?}
?? ?long long t = 1 % p;
?? ?for (long long i = 0; i < k; i ++ ){
?? ??? ?t = (long long)t * a % p;
?? ?}
?? ?for (long long i = 1,j = t; i <= k; i ++ ){
?? ??? ?if (mp.count(j)){
?? ??? ??? ?return (long long)i * k - mp[j];
?? ??? ?}
?? ??? ?j = (long long)j * t % p;
?? ?}
?? ?return -1;
}
int main(){
?? ?long long n,T;
?? ?cin >> n >> T;
?? ?if (T == 1){
?? ??? ?for (long long i = 1; i <= n; i ++ ){
?? ??? ??? ?long long a,b,p;
?? ??? ??? ?cin >> a >> b >> p;
?? ??? ??? ?cout << qmi(a,b,p) << endl;
?? ??? ?}
?? ?}?
?? ?else if (T == 2){
?? ??? ?for (int i = 1; ?i<= n; i ++ ){
?? ??? ??? ?int a,b,p;
?? ??? ??? ?cin >> a >> b >> p;
?? ??? ??? ?a %= p,b %= p;
?? ??? ??? ?if (a == 0 && b != 0){
?? ??? ??? ??? ?cout << "Orz, I cannot find x!" << endl;
?? ??? ??? ?}
?? ??? ??? ?else{
?? ??? ??? ??? ?cout << qmi(a,p - 2,p) * b % p << endl;
?? ??? ??? ?}
?? ??? ?}
?? ?}
?? ?else{
?? ??? ?for (long long i = 1; i <= n; i ++ ){
?? ??? ??? ?long long a,b,p;
?? ??? ??? ?cin >> a >> b >> p;
?? ??? ??? ?if (a % p == b % p){
?? ??? ??? ??? ?cout << 1 << endl;
?? ??? ??? ??? ?continue;
?? ??? ??? ?}
?? ??? ??? ?a %= p;
?? ??? ??? ?long long t = bsgs(a,b,p);
?? ??? ??? ?if (a == 0 && b == 0){
?? ??? ??? ??? ?cout << 1 << endl;
?? ??? ??? ?}
?? ??? ??? ?else if (a == 0 && b != 0){
?? ??? ??? ??? ?cout << "Orz, I cannot find x!" << endl;
?? ??? ??? ?}
?? ??? ??? ?else{
?? ??? ??? ??? ?if (t == -1){
?? ??? ??? ??? ??? ?cout << "Orz, I cannot find x!" << endl;
?? ??? ??? ??? ?}
?? ??? ??? ??? ?else{
?? ??? ??? ??? ??? ?cout << t << endl;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ?}
?? ?}
?? ?return 0;
}
```