Description

你被要求设计一个计算器完成以下三项任务：

、给定y,z,p,计算Y^Z Mod P 的值；

、给定y,z,p，计算满足xy≡ Z ( mod P )的最小非负整数；

、给定y,z,p，计算满足Y^x ≡ Z ( mod P)的最小非负整数。

Input

 输入包含多组数据。

第一行包含两个正整数T,K分别表示数据组数和询问类型（对于一个测试点内的所有数据，询问类型相同）。

以下行每行包含三个正整数y,z,p，描述一个询问。

Output

对于每个询问，输出一行答案。对于询问类型2和3，如果不存在满足条件的，则输出“Orz, I cannot find x!”，注意逗号与“I”之间有一个空格。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<queue>

#include<algorithm>

#include<map>

#include<cstring>

using namespace std;

#define duke(i,a,n) for(register int i = a;i <= n;i++)

#define lv(i,a,n) for(register int i = a;i >= n;i--)

#define clean(a) memset(a,0,sizeof(a))

#define int long long

const int INF =  << ;

typedef long long ll;

typedef double db;

template <class T>

void read(T &x)

{

    char c;

    bool op = ;

    while(c = getchar(), c < '' || c > '')

        if(c == '-') op = ;

    x = c - '';

    while(c = getchar(), c >= '' && c <= '')

        x = x *  + c - '';

    if(op) x = -x;

}

template <class T>

void write(T x)

{

    if(x < ) putchar('-'), x = -x;

    if(x >= ) write(x / );

    putchar('' + x % );

}

int t,k;

map <int,int> mp;

void work1(int y,int z,int p)

{

    int tot = ;

    while(z)

    {

        if(z & )

        {

            tot *= y;

            tot %= p;

        }

        y *= y;

        y %= p;

        z >>= ;

    }

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

}

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

{

    if(b == )

    {

        x = ;

        y = ;

        return a;

    }

    int t = exgcd(b,a % b,y,x);

    y -= (a / b * x);

    return t;

}

void work2(int y,int z,int p)

{

    int x,f;

    // z %= p;

    int d = exgcd(y,p,x,f);

    if(d != )

    {

        printf("Orz, I cannot find x!\n");

        return;

    }

    x = (x % p + p) % p;

    x = (x * z) % p;

    /*if(now == p)

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

    else*/

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

}

int qpow(int a,int b,int p)

{

    int tot = ;

    while(b)

    {

        if(b & )

        {

            tot *= a;

            tot %= p;

        }

        a *= a;

        a %= p;

        b >>= ;

    }

    return tot;

}

void work3(int a,int b,int p)

{

    if(a % p == )

    {

        printf("Orz, I cannot find x!\n");

        return;

    }

    mp.clear();

    int m = ceil(sqrt(p));

    int now = b % p,ans;

    mp[now] = ;

    duke(i,,m)

    {

        now = (now * a) % p;

        mp[now] = i;

    }

    int t = qpow(a,m,p);

    now = ;

    int ok = ;

    duke(i,,m)

    {

        now = (now * t) % p;

        if(mp[now])

        {

            ans = i * m - mp[now];

            printf("%lld\n",(ans % p + p) % p);

            ok = ;

            break;

        }

    }

    if(ok == )

    printf("Orz, I cannot find x!\n");

}

main()

{

    read(t);read(k);

    //cout<<t<<endl;

    duke(i,,t)

    {

        int y,z,p;

        read(y);read(z);read(p);

        if(k == )

        {

            work1(y,z,p);

        }

        else if(k == )

        {

            work2(y,z,p);

        }

        else if(k == )

        {

            work3(y,z,p);

        }

        //cout<<i<<" "<<t<<endl;

    }

    return ;

}