BSGS算法解析

前置芝士：

1.快速幂（用于求一个数的幂次方）

2.STL里的map（快速查找）

详解

BSGS 算法适用于解决高次同余方程 \(a^x\equiv b (mod p)\)

由费马小定理可得 x <= p-1

我们设 \(m = sqrt(p)\) 至于为什么写，下文会讲到。

那么\(x\)就可以用 \(m\) 表示出来。

即 x = \(k \times m - j\)

移项可得 \(a^t \equiv b\times a^j\) 其中 t = \(k \times m\)

这也就是我们为什么把\(x\)用 \(k \times m - j\)来表示。

因为改为加\(j\)后，移项后要求逆元，就会变得很麻烦。

这样，我们就可以枚举每个\(k\)和\(j\)，来判断左右两边得值是否相等就行了。

首先，我们可以枚举j 将 \(b\times a^j\)放入map中。

然后，从小到大枚举\(k\),在哈希表中，找到最大的\(j\)满足 \(a^t \equiv b\times a^j\) 其中 t = \(k \times m\)

若存在\(k\times m -j\)就是方程的解

关于上文中，为什么要设\(m = sqrt(p)\)

是为了保证BSGS的复杂度，是左右两边的数尽可能的均匀。

例题

P3846 [TJOI2007] 可爱的质数

模板题，水过去了

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

#include<cmath>

using namespace std;

#define LL long long

int a,b,p;

LL ksm(LL a, LL b)

{

	LL res = 1;

	for(; b; b >>= 1)

	{

		if(b & 1) res = res * a % p;

		a = a * a % p;

	}

	return res;

}

int BSGS(int a,int b,int p)

{

	map<LL,int> hash;  hash.clear();

	int m = (int)sqrt(p);

	for(int i = 0; i <= m; i++)

	{

		LL val = ksm(a,i) * b % p;//b * a ^ i

		hash[val] = i;//放入map中

	}

	a = ksm(a,m);//a ^ m

	for(int i = 0; i <= m; i++)

	{

		LL val = ksm(a,i);//(a^m)^i

		int j = hash.find(val) == hash.end() ? -1 : hash[val];//如果没有j就为-1

		if(j >= 0 && i * m - j >= 0) return i * m - j;//找到一组解

	}

	return -1;

}

int main()

{

	scanf("%d%d%d",&p,&a,&b);

	LL ans = BSGS(a,b,p);

	if(ans == -1) cout<<"no solution"<<endl;

	else printf("%lld\n",ans);

	return 0;

}

P2485 [SDOI2011]计算器

一道很多算法综合在一起的模板题，水过去了。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<map>

using namespace std;

#define LL long long

int t,opt,a,b,p,x,y;

inline int read()

{

	int s = 0, w = 1; char ch = getchar();

	while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}

	while(ch >= '0' && ch <= '9'){s = s * 10+ch -'0'; ch = getchar();}

	return s * w;

}

LL gcd(LL a, LL b)

{

	if(b == 0) return a;

	else return gcd(b,a%b);

}

LL ksm(LL a, LL b)//快速幂

{

	LL res = 1;

	for(; b; b >>= 1)

	{

		if(b & 1) res = res * a % p;

		a = a * a % p;

	}

	return res;

}

LL exgcd(int a,int b, int &x,int &y)//扩展欧几里得

{

	if(b == 0)

	{

		x = 1;

		y = 0;

        return a;

	}

	LL gcd = exgcd(b,a%b,y,x);

	y -= a / b * x;

	return gcd;

}

LL BSGS(LL a,LL b,LL p)//BSGS

{

	map<LL,int> hash; hash.clear();

	int m = (int) sqrt(p);

	b % p;

	for(int i = 0; i <= m; i++)

	{

		LL tmp = ksm(a,i) * b % p;

		hash[tmp] = i;

	}

	a = ksm(a,m);

	if(a == 0) return b == 0 ? 1 : -1;//特判当a为0的情况

	for(int i = 0; i <= m; i++)

	{

		LL tmp = ksm(a,i);

		int j = hash.find(tmp) == hash.end() ? -1 : hash[tmp];

		if(j >= 0 && i * m - j >= 0) return i * m - j;

	}

	return -1;

}

int main()

{

	t = read(); opt = read();

	while(t--)

	{

		a = read(); b = read(); p = read();

		if(opt == 1)

		{

			LL ans = ksm(a,b);

			printf("%lld\n",ans);

		}

		if(opt == 2)

		{

			LL k = exgcd(a,p,x,y);

			if(b % k) cout<<"Orz, I cannot find x!"<<endl;

			else printf("%lld\n",(x * (b/k) % p + p)%p);

		}

		if(opt == 3)

		{

			LL ans = BSGS(a,b,p);

			if(ans == -1) cout<<"Orz, I cannot find x!"<<endl;//无解情况

			else printf("%lld\n",ans);

		}

	}

	return 0;

}

巴特西

BSGS算法解析

前置芝士：

详解

例题

ENDING

最新文章

热门文章