求助BSGS
查看原帖
求助BSGS
425646
DreamsChaser楼主2021/2/13 17:57

最后两点没过,一直WA

#include <bits/stdc++.h>
#define int long long

using namespace std;

int mul(int a,int b,int P){
    int L=a*(b>>25LL)%P*(1LL<<25)%P;
    int R=a*(b&((1LL<<25)-1))%P;
    return (L+R)%P;
}

int power(int a,int b,int p) {
	if(b==0) return 1;
	int tmp=power(a,b/2,p);
	if(b%2==0) return tmp*tmp%p;
	return tmp*tmp%p*a%p;
}

int BSGS(int a,int b,int p) {
	unordered_map<int,int> hash;hash.clear();
	b %= p;
	int t=ceil(sqrt(p));
	for(int i=0; i<t; i++) hash[mul(b,power(a,i,p),p)]=i;
	a=power(a,t,p);
	if(a==0) return b==0?1:-1;
	for(int i=0; i<=t; i++) {
		int val=power(a,i,p);
		int j=hash.find(val)==hash.end()?-1:hash[val];
		if(j>=0 && i*t-j>=0) return i*t-j; 
	}
	return -1;
}

signed main() {
    int m,K;
    scanf("%lld%lld",&K,&m);
    printf("%lld\n",BSGS(10,(9*K+1)%m,m));
	return 0;
}

开了c++11,想问问大佬哪里错了

2021/2/13 17:57
加载中...