该题的第三个样例输入的第二行是:
2 1 3
它的的模数是3,将其提到前面去变为3 2 1.
样例输出是:
0
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL A,B,P,M;
unordered_map<LL,LL>mp;
LL gsc(LL xx,LL pp,LL mod){
if(xx==1||pp==0)return 1;
if(xx==0||pp==1)return xx;
LL ret=1;for(;pp;pp>>=1,xx=(xx*xx)%mod)if(pp&1)ret=(ret*xx)%mod;
return ret;
}
int main(){
cin>>P>>A>>B;M=sqrt(P)+1;
LL QWQ=1;
for(int i=0;i<M;i++){
mp[(B*QWQ)%P]=i;QWQ=QWQ*A%P;
}
LL QAQ;
QWQ=QAQ=gsc(A,M,P);
for(int i=1;i<=M;i++){
if(mp.count(QWQ%P)){cout<<M*i-mp[QWQ%P];return 0;}
QWQ=(QWQ*QAQ)%P;
}
puts("no solution");
return 0;
}
它的输出却是2。
甚至我的这个连第三个样例都过不了的代码可以AC!(同样也是输出2)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
map<LL,LL>mp;
LL gsc(LL X,LL P,LL MOD){LL ret=1;for(;P;P>>=1,X=(X*X)%MOD)if(P&1)ret=(ret*X)%MOD;return ret;}
LL BabyStepGaintStep(LL A,LL B,LL P){
A%=P;B%=P;
LL ans=-1;mp.clear();
LL M=sqrt(P)+1;
LL QWQ=1,QAQ=gsc(A,M,P);
for(LL i=0;i<M;i++)
mp[(B*QWQ)%P]=i,QWQ=QWQ*A%P;
QWQ=QAQ;
for(LL i=1;i<=M;i++){
if(mp.count(QWQ%P)){
ans=(M*i-mp[QWQ%P]+P)%P;
break;
}
QWQ=(QWQ*QAQ)%P;
}
return ans;
}
int main(){
LL T,op;cin>>T>>op;
while(T--){
LL A,B,P;cin>>A>>B>>P;
if(op==1){
cout<<gsc(A,B,P)<<endl;
}else if(op==2){
if(A%P==0&&B%P!=0){cout<<"Orz, I cannot find x!\n";continue;}
cout<<B*gsc(A,P-2,P)%P<<endl;
}else if(op==3){
if(A%P==0&&B%P!=0){cout<<"Orz, I cannot find x!\n";continue;}
LL ans=BabyStepGaintStep(A,B,P);
if(ans==-1)cout<<"Orz, I cannot find x!\n";
else cout<<ans<<endl;
}
}
return 0;
}
有没有大佬能告诉我为什么我写法和部分题解的写法会炸?顺便请求加强数据。并且撤下部分模板题解