Description
你被要求设计一个计算器完成以下三项任务：
1、给定y,z,p,计算Y^Z Mod P 的值；
2、给定y,z,p，计算满足xy≡ Z ( mod P )的最小非负整数；
3、给定y,z,p，计算满足Y^x ≡ Z ( mod P)的最小非负整数。
Input
输入包含多组数据。
第一行包含两个正整数T,K分别表示数据组数和询问类型（对于一个测试点内的所有数据，询问类型相同）。
以下行每行包含三个正整数y,z,p，描述一个询问。
Output
对于每个询问，输出一行答案。对于询问类型2和3，如果不存在满足条件的，则输出“Orz, I cannot find x!”，注意逗号与“I”之间有一个空格。
Sample Input
【样例输入1】
3 1
2 1 3
2 2 3
2 3 3
【样例输入2】
3 2
2 1 3
2 2 3
2 3 3
【数据规模和约定】
对于100%的数据，1<=y,z,p<=10^9，为质数，1<=T<=10。
3 1
2 1 3
2 2 3
2 3 3
【样例输入2】
3 2
2 1 3
2 2 3
2 3 3
【数据规模和约定】
对于100%的数据，1<=y,z,p<=10^9，为质数，1<=T<=10。
Sample Output
【样例输出1】
2
1
2
【样例输出2】
2
1
0
2
1
2
【样例输出2】
2
1
0
HINT
Source
第一轮day1
快速幂+exgcd+BSGS~
看起来长，实际上很好写~
注意：
（1）BSGS和exgcd里面有一部分结果要开long long；
（2）BSGS的输出答案要+c%c防止变成负数.
#include<cstdio>
#include<cmath>
#include<map>
using namespace std;
#define ll long longint t,k,a,b,c,x,y;
ll ans,now;
map<ll,int> ma;int read()
{int totnum=0;char ch=getchar();while(ch<'0' || ch>'9') ch=getchar();while(ch>='0' && ch<='9') {totnum=(totnum<<1)+(totnum<<3)+ch-'0';ch=getchar();}return totnum;
}ll mi(ll u,ll v)
{ll now=1;u%=c;while(v){if(v&1) now=now*u%c;u=u*u%c;v>>=1;}return now;
}void exgcd(int u,int v,int &x,int &y)
{if(!v){x=1;y=0;return;}exgcd(v,u%v,x,y);int z=x;x=y;y=z-u/v*y;
}int gcd(int u,int v)
{return v ? gcd(v,u%v):u;
}void do2()
{c=-c;int n=gcd(a,c);if(b%n){printf("Orz, I cannot find x!\n");return;}a/=n;b/=n;c/=n;exgcd(a,c,x,y);x=(ll)x*b%c;while(x<0) x+=c;printf("%d\n",x);
}void do3()
{if(!(a%c)){printf("Orz, I cannot find x!\n");return;}ma.clear();int m=sqrt(c);if(m*m!=c) m++;ans=b%c;ma[ans]=0;for(int i=1;i<=m;i++){ans=ans*a%c;ma[ans]=i;}now=mi(a,m);ans=1;for(int i=1;i<=m;i++){ans=ans*now%c;if(ma[ans]){now=i*m-ma[ans];printf("%lld\n",((now%c)+c)%c);return;}}printf("Orz, I cannot find x!\n");
}int main()
{t=read();k=read();while(t--){a=read();b=read();c=read();if(k==1) printf("%d\n",mi(a,b));else if(k==2) do2();else do3();}return 0;
}