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。
Sample Output
【样例输出1】
2
1
2【样例输出2】
2
1
0
题解
这题其实就是来巩固数论知识的。。
第一问快速幂不会右转百度
第二问扩展欧几里得不会右转百度，观察题目发现p是质数于是还可以用欧拉
重点在第三问因为我没有学过高次同余方程。。这里我就口胡一下BSGS算法吧
还是因为p是质数，实质上给BSGS减了一些复杂度。根据费马小定理可以知道答案一定不超过p
因为不会打恒等号我就用等号代替了
设m为sqrt(p) 向上取整，那么次数可以表示为k*m+c。
原式可以化为y^k*m+c=z(mod p)
再化简得到(y^k*m) * (y^c)=z(mod p)
移项得y^k*m=z*(y^-c) (mod p)
即为y^k*m=z*(y^c的逆元) (mod p)
其中c＜m，右半部分我们可以暴力出来他们的值，拿一个map记录一下
暴力完后枚举k，判一下map中有没有这个值，有就输出。。否则枚举完后输出无解
y^c的逆元可以用y^c-1的逆元递推求出
如此就是BSGS的思想啦，对于这题就足够了。那么p非质数的情况请大家右转百度
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
typedef long long LL;
LL exgcd(LL a,LL b,LL &x,LL &y)
{if(a==0){x=0;y=1;return b;}else{LL tx,ty;LL d=exgcd(b%a,a,tx,ty);x=ty-(b/a)*tx;y=tx;return d;}
}
int pow_mod(int a,int b,int mod)
{int ans=1%mod;a%=mod;while(b){if(b%2==1)ans=(LL)ans*a%mod;a=(LL)a*a%mod;b/=2;}return ans;
}
map<int,int> mp;
void BSGS(int y,int z,int mod)
{if(y==0&&z==0){
printf("1\n");return;} if(y==0&&z!=0){
printf("Orz, I cannot find x!\n");return;}mp.clear();int k=ceil(sqrt(mod)),tmp=1,p=pow_mod(y,mod-2,mod);mp[z]=k+1;for(int i=1;i<k;i++){tmp=(LL)tmp*p%mod;int t=(LL)tmp*z%mod;if(mp[t]==0)mp[t]=i;}tmp=1;p=pow_mod(y,k,mod);for(int i=0;i<k;i++){if(mp[tmp]){if(mp[tmp]==k+1)printf("%d\n",i*k);else printf("%d\n",i*k+mp[tmp]);return ;}tmp=(LL)tmp*p%mod;}printf("Orz, I cannot find x!\n");return ;
}
int main()
{int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){int p,q,op;scanf("%d%d%d",&p,&q,&op);p%=op;if(k==1)printf("%d\n",pow_mod(p,q,op));else if(k==2){LL a=p,b=op,K=q,x,y;LL d=exgcd(a,b,x,y);if(k%d!=0){
printf("Orz, I cannot find x!\n");continue;}x=((x*(K/d))%(b/d)+(b/d))%(b/d);printf("%lld\n",x);}else q%=op,BSGS(p,q,op);}return 0;
}