exBSGS 求条,玄关
查看原帖
exBSGS 求条,玄关
656427
iamsh楼主2025/8/1 15:28

exBSGS 板子,但是该数据下出错了 input:

46 40 36
10 48 4
0 0 0

answer:

2
2

output:

No Solution
No Solution

感觉是 exBSGS 函数里的判断有问题

// Code by iamsh

#include<bits/stdc++.h>
using namespace std;
long long BSGS(long long a,long long b,long long p) {
	// cout << a << " " << b << " " << p << "\n";
	if(p == 1) {
		return 0;
	}
	long long A = sqrtl(p) + 1,c = 1;
	unordered_map<long long,long long> mp;
	for(long long n = 0;n <= A;n ++) {
		mp[b % p] = n,b = b * a % p;
		if(n) {
			c = c * a % p;
		}
	}
	b = c;
	for(long long m = 1;m <= A;m ++) {
		if(mp.count(b)) {
			return m * A - mp[b];
		}
		b = b * c % p;
	}
	return -1;
}
long long exgcd(long long a,long long b,long long &x,long long &y) {
	if(!b) {
		x = 1,y = 0;
		return a;
	}
	long long ans = exgcd(b,a % b,y,x);
	y -= a / b * x;
	return ans;
}
long long exBSGS(long long a,long long b,long long p) {
	if(p == 1 || b % p == 1) {
		return 0;
	}
	if(a % p == b % p) {
		return 1;
	}
	long long x,y,s = 1,k = 0;
	long long g = exgcd(a,p,x,y);
	while(g > 1) {
		// cout << a << " " << b << " " << p << "\n";
		// cout << b << " " << g << "\n";
		if(b % g) {
			return -1;
		}
		k ++,b /= g,p /= g;
		s = a / g * s % p;  
		g = exgcd(a,p,x,y);
	}
	exgcd(s,p,x,y);
	b = b * (x % p + p) % p;
	long long res = BSGS(a,b,p);
	return res < 0 ? res : res + k;
}
void solve() {
	long long p,a,b;
	cin >> a >> p >> b;
	if(!p && !a && !b) {
		exit(0);
	}
	long long res = exBSGS(a,b,p);
	if(res < 0) {
		cout << "No Solution\n";
	}
	else {
		cout << res << "\n";
	}
}
int main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cout << fixed << setprecision(12);
	int t = 1e9;
//	cin >> t;
	while(t --) {
		solve();
	}
	return 0;
}
2025/8/1 15:28
加载中...