Description:

Solution:

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<map>

using namespace std;

typedef long long ll;

int testcases,k;

int y,z,p;

ll power(ll a,ll b,ll m)

{

    ll res = 1;

    while(b > 0)

    {

        if(b & 1)res = (res * a) % m;

        a = (a * a) % m;

        b = b >> 1;

    }

    return res;

}

int gcd(int a,int b){return (b == 0 ? a : gcd(b,a % b));}

ll exgcd(ll a,ll b,ll &x,ll &y)

{

    if(b == 0)

    {

        x = 1;

        y = 0;

        return a;

    }

    ll g = exgcd(b,a % b,y,x);

    y -= a / b * x;

    return g;

}

void BSGS(ll a,ll b,ll p)

{

    map<int,int> hash;

    hash.clear();

    b %= p;

    ll t = (ll)sqrt(p) + 1;

    for(int i = 0;i < t;++i)

    {

        hash[(ll)b * power(a,i,p) % p] = i;

    }

    a = power(a,t,p);

    if(a == 0)

    {

        if(b == 0)

        {

            puts("1");

        }

        else

        {

            puts("Orz, I cannot find x!");

        }

        return;

    }

    for(int i = 0;i <= t;++i)

    {

        int v = power(a,i,p);

        int j = hash.find(v) == hash.end() ? -1 : hash[v];

        if(j >= 0 && i * t - j >= 0)

        {

            printf("%lld\n",i * t - j);

            return;

        }

    }

    puts("Orz, I cannot find x!");

    return;

}

int main()

{

    scanf("%d%d",&testcases,&k);

    for(int i = 1;i <= testcases;++i)

    {

        scanf("%d%d%d",&y,&z,&p);

        switch (k)

        {

            case 1:

            {

                printf("%lld\n",power((ll)y,(ll)z,(ll)p));

                break; 

            }

            case 2:

            {

                int g = gcd(y,p);

                if(z % g == 0)

                {

                    y /= g;p /= g;z /= g;

                    ll x,k;

                    exgcd((ll)y,(ll)p,x,k);

                    x *= z;

                    while(x < 0)x += (ll)p;

                    x %= p;

                    printf("%lld\n",x);

                }

                else

                {

                    puts("Orz, I cannot find x!");

                }

                break;

            }

            case 3:

            {

                BSGS((ll)y,(ll)z,(ll)p);

                break;

            }

        }

    }

    return 0;

}