Baby Step,Giant Step算法模板-白红宇

Baby Step,Giant Step算法模板

阅读量：7000 次

发布时间：2019-06-27

本文共 772 字，大约阅读时间需要 2 分钟。

介绍：BSGS（Baby Step，Giant Step）算法是用来求高次同余方程 $a^x\equiv b(mod P)$ 的解的算法。

模板：P148

//baby step giant step#include
    
     #include
     #include
      
       using namespace std;typedef long long ll;ll q_pow(ll a,ll b,ll M){	ll res = 1;	while(b > 0){		if(b&1) res = res*a%M;		a = a*a%M;		b >>= 1;	}	return res%M;}int BSGS(ll a,ll b,ll p){	map
       
         hash;	hash.clear();	int t = (int)sqrt(p)+1;	for(int j = 0;j < t;j++){		int val = b*q_pow(a,j,p)%p;		hash[val] = j;	}		a = q_pow(a,t,p);//a = a^t	for(int i = 0;i <= t;i++){		int val = q_pow(a,i,p);		if(hash.count(val) && i*t-hash[val]>0)			return i*t-hash[val];//hash[val] = j;	}	return -1;//无解 }int main(){	int a,b,x,p;	cin >> a >> b >> p;	cout << BSGS(a,b,p);	return 0;}

转载于:https://www.cnblogs.com/long98/p/10352166.html

你可能感兴趣的文章