计算器（BSGS，快速幂，exgcd）

这个题目坑啊，查来查去，排查了好久，发现自己快速幂写错了。。。

这个题目有三个询问

1、$y^z$ $mod$ $p$

2、$xy$ ≡ $z(mod$ $p)$ （求x）

3、$y^x ≡z(mod$ $p)$（求x）

第一个用快速幂求。

第二个就是裸的ecgcd，见 同余方程

前两个是35分

第三个就是裸的BSGS 详见他人博客(鸣谢)

三个任务分别对应solve1,solve2,solve3

#include <bits/stdc++.h>
using namespace std ;#define rep(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define REP(i,a,b) for (int (i)=(a);(i)>=(b);(i)--)
#define Rep(i,x)   for (int (i)=head[x];(i);i=next[i])#define lowbit(x) ((x)&(-(x)))
#define sqr(x) ((x)*(x))
#define clr(a) memset((a),0,sizeof((a)))
#define ls ((x)<<1)
#define rs ((x)<<1|1)
#define mid (((l)+(r))>>1)
//#define mp make_pair
#define pb push_back
#define fi first
#define se secondtypedef long long ll ;ll n,k,y,z,p  ;
map<ll,ll> mp;map<int,int>a;
ll ksm(ll a,ll b,int p){ll res=1;for(;b;b>>=1,a=a*a%p) if(b&1) res=res*a%p;return res;
}ll exgcd(ll a,ll b,ll &x,ll &y){if (b==0){x=1;y=0;return a ;}ll ans=exgcd(b,a%b,y,x) ;y-=x*(a/b) ;return ans ;
}void solve1(ll y,ll z,ll p){printf("%lld\n",ksm(y,z,p)) ;return  ;
}void solve2(ll yy,ll zz,ll p){if (yy==0 && zz!=0){printf("Orz, I cannot find x!\n") ;return  ;}ll x,y ;ll t=exgcd(yy,p,x,y) ;if (zz%t){printf("Orz, I cannot find x!\n") ;return  ;}x=((zz/t*x%p)+p)%(p/t);printf("%lld\n",x) ;return  ;
}void solve3(ll x,ll z,ll mod){map<int,int>a;ll k=1,y=z%mod;x%=mod;if(!x&&!z){puts("1");return ;}if(!x){printf("Orz, I cannot find x!\n");return ;}ll m=ceil(sqrt(mod-1));ll ni=ksm(x,m,mod);ni=ksm(ni,mod-2,mod);a.clear();a[1]=m+1;for(ll j=1;j<m;j++){k=k*x%mod;if(!a[k]) a[k]=j;}for(ll i=0;i<m;i++){ll u=a[y];if(u){if(u==m+1) printf("%lld\n",i*m);else printf("%lld\n",i*m+u);return ;}y=y*ni%mod;}printf("Orz, I cannot find x!\n");
}
int main(){while(scanf("%lld%lld",&n,&k)!=EOF){rep(i,1,n){ll y,z,p ;scanf("%lld%lld%lld",&y,&z,&p) ;if (k==1) solve1(y,z,p) ;else if (k==2) solve2(y,z,p) ;else solve3(y,z,p) ;}} 
}