「学习笔记」BSGS

点击查看目录

目录
「学习笔记」BSGS
Baby-step Giant-step
问题
算法
例题
Discrete Logging
代码
P3306 [SDOI2013] 随机数生成器
思路
P2485 [SDOI2011]计算器
思路
Matrix
思路
代码

Baby-step Giant-step

问题

在 \(O(\sqrt{p})\) 的时间内求解

\[a^x \equiv b \pmod p \]

其中 \(a\perp p\)，方程的解 \(x\) 满足 \(0 \le x < p\)。

算法

首先根据费马小定理 \(a^{p-1}\equiv1\pmod{p}\)，不难发现 \(1\sim p-1\) 是一个循环节，也就是说只用判断 \(1\sim p-1\) 这些数里是否存在一个方程的解 \(x\) 即可。

但是这个范围仍然很大，直接 \(O(p)\) 跑肯定不行。

令 \(x=A\left\lceil\sqrt{p}\right\rceil-B (0\le A, B\le\left\lceil\sqrt{p}\right\rceil)\)，则 \(a^{A\left\lceil\sqrt{p}\right\rceil-B} \equiv b \pmod p\)。

则 \(a^{A\left\lceil\sqrt{p}\right\rceil} \equiv a^{B} b \pmod p\)。

由于 \(A,B\) 不大，我们可以枚举出所有 \(a^{B} b\) 和 \(a^{A\left\lceil\sqrt{p}\right\rceil}\) 的取值。用 map 存下所有 \(a^{B} b\) 的取值，再查找 \(a^{A\left\lceil\sqrt{p}\right\rceil}\) 的取值是否出现过即可。

注意在求出满足 \(a^{A\left\lceil\sqrt{p}\right\rceil} \equiv a^{B} b \pmod p\) 的合法 \(A,B\) 后还要推回到 \(a^{A\left\lceil\sqrt{p}\right\rceil-B} \equiv b \pmod p\) 才能得到解 \(x=A\left\lceil\sqrt{p}\right\rceil-B (0\le A, B\le\left\lceil\sqrt{p}\right\rceil)\)，这一步要求 \(a\perp p\)，但不要求 \(p\in\mathbb{P}\)。

时间复杂度：\(O(\sqrt{p}\log_2\sqrt{p})\)。

你想更快的话你用哈希表也行。

例题

Discrete Logging

板子题，放一份代码。

代码

点击查看代码

inline ll FastPow (ll a, ll b, ll P) {
	ll ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % P;
		a = a * a % P, b >>= 1;
	}
	return ans;
}
inline void Solve () {
	ll qp = ceil (sqrt (p));
	_for (i, 0, qp) h[n * FastPow (b, i, p) % p] = i;
	ll t = FastPow (b, qp, p), num = 1;
	_for (i, 1, qp) {
		num = num * t % p;
		if (h[num]) {
			ans = (i * qp % p - h[num] + p) % p;
			return;
		}
	}
	return;
}

P3306 [SDOI2013] 随机数生成器

思路

推式子题。

\[\begin{aligned} x_{i} &\equiv x_{i-1}a+b \pmod{p}\\ &\equiv (x_{i-2}a+b)a+b \pmod{p}\\ &\equiv x_{i-2}a^2+ab+b \pmod{p}\\ &\equiv (x_{i-3}a+b)a^2+ab+b \pmod{p}\\ &\equiv x_{i-3}a^3+a^2b+ab+b \pmod{p}\\ &\equiv x_{1}a^{i-1}+b(\sum_{k=0}^{i-2}a^{k}) \pmod{p}\\ &\equiv x_{1}a^{i-1}+b\frac{1-a^{i-2}}{1-a} \pmod{p}\\ \end{aligned} \]

那么：

\[\begin{aligned} x_{1}a^{i-1}+b\frac{a^{i-1}-1}{a-1} &\equiv t \pmod{p}\\ x_{1}a^{i-1}+\frac{a^{i-1}b}{a-1} - \frac{b}{a-1} &\equiv t \pmod{p}\\ a^{i-1}(x_{1}+\frac{b}{a-1}) &\equiv t + \frac{b}{a-1} \pmod{p}\\ a^{i-1} &\equiv \frac{t + \frac{b}{a-1}}{x_{1}+\frac{b}{a-1}} \pmod{p}\\ \end{aligned} \]

令 \(i - 1 = A \left \lceil \sqrt p \right \rceil - B\)，则 \(a^{A \left \lceil \sqrt p \right \rceil - B} \equiv \dfrac{t + \frac{b}{a-1}}{x_{1}+\frac{b}{a-1}} \pmod{p}\)。

则：

\[\begin{aligned} a^{A \left \lceil \sqrt p \right \rceil} &\equiv a^{B}\dfrac{t + \frac{b}{a-1}}{x_{1}+\frac{b}{a-1}} \pmod{p} \end{aligned} \]

就可以跑 BSGS 了。

但是还有几个细节：

\(x1=t\)：答案为 \(1\)。
\(a=0\)：如果 \(b=t\)，答案为 \(2\)，否则为 \(-1\)。
\(a=1\)：此时 \(x_i=x_1+(i-1)b\)，算逆元即可。

P2485 [SDOI2011]计算器

思路

是不是再来一个 CRT 就同余全家桶了。

裸的逆元和 BSGS，但是题目只保证 \(p\in\mathbb{P}\) 不保证 \(y\perp p\)，需要特判一下 \(p\) 是否为 \(y\) 的倍数。

if (!y) { ans = (z % p ? -1 : 1); return; }

Matrix

思路

定义一个矩阵的类然后直接跑就行，感觉没啥大区别。

代码

点击查看代码

const ll N = 110;
namespace SOLVE {
	ll n, p, ans;
	class Matrix {
	public:
		ll len, m, ma[N][N];
		inline void Init (ll l, ll md) {
			len = l, m = md;
			memset (ma, 0, sizeof (ma));
			_for (i, 1, l) ma[i][i] = 1;
			return;
		}
		inline void Print () {
			_for (i, 1, n) {
				_for (j, 1, n) {
					printf ("%lld ", ma[i][j]);
				}
				puts ("");
			}
			puts ("");
			return;
		}

		ll* operator [] (ll x) { return ma[x]; }
		Matrix operator * (Matrix another) const {
			Matrix ans;
			ans.Init (len, m);
			memset (ans.ma, 0, sizeof (ans.ma));
			_for (i, 1, len) _for (j, 1, len) _for (k, 1, len)
				ans[i][j] = (ans[i][j] + ma[i][k] * another[k][j] % m) % m;
			return ans;
		}
		bool operator == (Matrix another) const {
			_for (i, 1, n) _for (j, 1, n) if (ma[i][j] != another[i][j]) return 0;
			return 1;
		}
		bool operator < (Matrix another) const {
			_for (i, 1, len) _for (j, 1, len) {
				if (ma[i][j] < another[i][j]) return 1;
				if (ma[i][j] > another[i][j]) return 0;
			}
			return 0;
		}
	} a, b;
	std::map <Matrix, ll> mp;

	inline ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}

	inline Matrix FastPow (Matrix a, ll b, ll P) {
		Matrix ans;
		ans.Init (n, P);
		while (b) {
			if (b & 1) ans = ans * a;
			a = a * a, b >>= 1;
		}
		return ans;
	}

	inline void In () {
		n = rnt (), p = rnt ();
		a.Init (n, p), b.Init (n, p);
		_for (i, 1, n) _for (j, 1, n) a[i][j] = rnt ();
		_for (i, 1, n) _for (j, 1, n) b[i][j] = rnt ();
		return;
	}
	inline void Solve () {
		ll qp = ceil (sqrt (p));
		_for (i, 0, qp) mp[b] = i, b = b * a;
		a = FastPow (a, qp, p);
		Matrix mat; mat.Init (n, p);
		_for (i, 1, qp) {
			mat = mat * a;
			if (mp[mat]) {
				ans = (i * qp % p - mp[mat] + p) % p;
				return;
			}
		}
		return;
	}
	inline void Out () {
		printf ("%lld\n", ans);
		return;
	}
}