• 对于问题①，用快速幂
• 对于问题②，用exgcd
• 对于问题③，用bsgs

挖个坑，以后复习时来补充

#include <bits/stdc++.h>
#define int long long
using namespace std;

int quick_pow(int a,int b,int m)
{
    if(b == 0) return 1;
    int ans = quick_pow(a,b/2,m);
    ans = ans*ans%m;
    if(b%2!=0) ans = ans*a%m;
    return ans;

}

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

int bsgs(int a,int b,int p)
{
    map<int,int> hash;
    hash.clear();
    b%=p;
    int t = sqrt(p)+1;
    for(int i=0;i<t;i++)
        hash[b*quick_pow(a,i,p)%p] = i;
    a = quick_pow(a,t,p);
    if(!a) return b==0?1:-1;
    for(int i=1;i<=t;i++)
    {
        int val = quick_pow(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;
}

signed main()
{
    int t,k;
    cin >> t >> k;
    while(t--)
    {
        int a,b,p;
        cin >> a >> b >> p;
        if(k == 1) cout << quick_pow(a,b,p);
        if(k == 2)
        {
            int x,y;
            int ans = exgcd(a,p,x,y);
            if(b%ans) cout << "Orz, I cannot find x!";
            else
            {
                int temp=p/ans;
                while(x<0) x+=temp;
                cout << ((x*b/ans)%temp+temp)%temp;
            }
        }
        if(k == 3)
        {
            if(bsgs(a,b,p) == -1) cout << "Orz, I cannot find x!";
            else cout << bsgs(a,b,p);
        }
        cout << endl;
    }
    return 0;
}