2个错
1、扩欧忘了写return,查错2小时
2、把a,b的值对p求余时,要写到里面,因为第一问,不需要,幂要求是原值。
#include <cstdio>
#include <map>
#include <cmath>
using namespace std;
typedef long long LL;
int a,b,p;
LL qmi(int a,int b,int p){
LL res=1%p;
while(b){
if(b&1) res=res*a%p;
b>>=1;
a=(LL)a*a%p;
}
return res;
}
void exgcd(int a,int b,LL &x,LL &y){
if(b==0){
x=1,y=0;
return;//千万别忘了return,否则会导致自动退出的错误。
}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
LL inv(int a,int p){
if(a==0) return -1;
LL x,y;
exgcd(a,p,x,y);
return (x%p+p)%p;
}
LL bsgs(int a,int b,int p){
if(a==0 || b==0) return -1;
map<LL,LL> mp;
LL m=ceil(sqrt(p));
LL t=1;
for(int i=0;i<m;i++){
if(t!=b) mp[t]=i;
else return i;
t=t*a%p;
}
for(int i=0;i<m;i++){
LL now=b*inv(qmi(a,m*i,p),p)%p;
if(!mp.count(now)) continue;
LL ans=i*m+mp[now];
return ans;
}
return -1;
}
int main(){
int T,K;
scanf("%d%d",&T,&K);
while(T--){
scanf("%d%d%d",&a,&b,&p);
if(K==1){
printf("%lld\n",qmi(a,b,p));
}
else if(K==2){
a%=p,b%=p;//不能写外面,k==1时,会改变幂,导致错误
LL ans=b*inv(a,p)%p;
if(ans<0){
puts("Orz, I cannot find x!");
}
else printf("%lld\n",ans);
}
else if(K==3){
a%=p,b%=p;
LL ans=bsgs(a,b,p);
if(ans<0){
puts("Orz, I cannot find x!");
}
else printf("%lld\n",ans);
}
}
return 0;
}
我是傻逼