请求加强数据
查看原帖
请求加强数据
999274
CNS_5t0_0r2楼主2024/7/8 10:46

这份代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
unordered_map<int,int> Hash;
struct triple{
	int x,y,z;
	triple(int _x_,int _y_,int _z_){x = _x_;y = _y_;z = _z_;}
};
triple exgcd(int a,int b){
	if(b == 0)
		return triple(1,0,a);
	triple last = exgcd(b,a % b);
	return triple(last.y,last.x - a / b * last.y,last.z);
}
int BSGS(int b,int n,int p){
	int m = (int)ceil(sqrt(p));
	Hash.clear();
	int base = 1;
    //预处理
	for(int i = 0;i < m;i++){
		Hash[base] = i;
		if(base == n)
		    return i;
		base = base * b % p;
	}
	int d = 1;
	for(int i = 0;i < m;i++){
		triple res = exgcd(d,p);
		int C = p / res.z;
		res.x = (res.x * n / res.z % C + C) % C;
		int j = Hash[res.x];
		if(j != 0)//如果b^j mod p存在,返回 
			return i * m + j;
		d = d * base % p;//此时base的值为b^m
	}
	return -1;
}
int p,b,n;
signed main(){
	cin >> p >> b >> n;
	b %= p;n %= p;
	int ans = BSGS(b,n,p);
	if(ans == -1)
		cout << "no solution";
	else
		cout << ans;
	return 0;
}

在这一个地方:int m = (int)ceil(sqrt(p)),把 ceil 去掉也可通过,故请求加强。

2024/7/8 10:46
加载中...