虽然AC了,但我BSGS好像写假了?而且数据好像太水?
查看原帖
虽然AC了,但我BSGS好像写假了?而且数据好像太水?
754467
f_hxr_楼主2024/1/24 14:11

该题的第三个样例输入的第二行是:

2 1 3

它的的模数是3,将其提到前面去变为3 2 1.

样例输出是:

0

但我将该数据输入我自己在模版的AC代码里

#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。

不但如此,模板的第一篇题解和第五篇题解的输出都是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;
} 

有没有大佬能告诉我为什么我写法和部分题解的写法会炸?顺便请求加强数据。并且撤下部分模板题解

2024/1/24 14:11
加载中...