BSGS（大步小步）算法学习笔记

前置芝士

会取模运算就行啦！

正文部分

拔山盖世 $\tt{BSGS}$ 算法用于求解 $a^x \equiv b \pmod{p}, \ a \perp p$ 中 $x$ 的值。

设 $x = ti - j$，$t = \left \lceil \sqrt{p} \right \rceil$，$1 \le i \le t$，$0 \le j < t$。

然后简单化一下：

$$a^{ti-j} \equiv b \ \ \ \ \Rightarrow \ \ \ \ a^{ti} \equiv ba^j \pmod{p}$$

因为 $ba^j$ 只有 $t$ 个取值，可以先枚举 $j$ ，求出所有的 $ba^j$ 并使用 $\tt{Hash}$ 或 $\tt{map}$ 存储，然后枚举 $i$，求出 $a^{ti}$，查找是否有与之相等的 $ba^j$ ，若有则 $ti-j$ 即为合法的 $x$ 值。不算 $\tt{Hash}$ 或 $\tt{map}$ 的化，复杂度 $\Theta(\sqrt{p})$。

CODE

int Pow(int x, int k, int p, int r = 1) {
	for (; k; k >>= 1, x = x * x % p) {
		if (k & 1) r = r * x % p;
	}
	return r;
}

int bsgs(int a, int b, int p) {
	b %= p, a %= p;
	map<int, int> m;
	int t = ceil(sqrt(p)), k = 1;
	for (int i = 0; i < t; i ++, k = k * a % p) {
		m[k * b % p] = i;
	}
	a = Pow(a, t, p), k = a;
	for (int i = 1; i <= t; i ++, k = k * a % p) {
		if (m.find(k) == m.end()) continue;
		if (i * t - m[k] >= 0) return i * t - m[k];
	}
	return -1;
}

exBSGS

使用 $\tt{BSGS}$ 有一个限制条件，即 $a \perp p$，$\tt{exBSGS}$ 就是为了解决这个问题。

考虑 $a$、$p$ 不互质时怎么做，设 $g = \gcd(a,p)$，$a = a’g$，$p=p’g$，易得 ：

$$a'^xg^x-kp'g=b$$ $$\Rightarrow g \left( a'^x g^{x-1} - kp'\right) = b$$ $$\Rightarrow g \mid b$$

得到有解的条件：$g \mid b$。 然后继续瞎搞一波：

$$a^x \equiv b \pmod{p}$$ $$\Rightarrow \dfrac{a^x}{g} \equiv \dfrac{b}{g} \pmod{p'}$$ $$\Rightarrow a' \times a^{x -1} \equiv \dfrac{b}{g} \pmod{p'}$$ $$\Rightarrow a^{x-1} \equiv \dfrac{b}{g} \times a'^{-1} \pmod{p'}$$

每次使 $b = \dfrac{b}{g} \times a’^{-1} $，$p = p’$，缩小问题范围，一直做到 $a$，$p$ 互质即可 $\tt{BSGS}$ 求解。注意 $a$ 的指数变为 $x-1$。

CODE

int Pow(int x, int k, int p, int r = 1) {
	for (; k; k >>= 1, x = x * x % p) {
		if (k & 1) r = r * x % p;
	}
	return r;
}

void exgcd(int a, int b, int &x, int &y) {
	if (b == 0) {x = 1, y = 0; return;};
	exgcd(b, a % b, x, y);
    int t = y; y = x - (a / b) * y, x = t;
}

int Inv(int x, int p, int a = 0, int b = 0) {
	return exgcd(x, p, a, b), (a % p + p) % p;
}

int gcd(int a, int b) {
	return (!b ? a : gcd(b, a % b));
}

int bsgs(int a, int b, int p) {
	b %= p, a %= p;
	map<int, int> m;
	int t = ceil(sqrt(p)), k = 1;
	for (int i = 0; i < t; i ++, k = k * a % p) {
		m[k * b % p] = i;
	}
	a = Pow(a, t, p), k = a;
	for (int i = 1; i <= t; i ++, k = k * a % p) {
		if (m.find(k) == m.end()) continue;
		if (i * t - m[k] >= 0) return i * t - m[k];
	}
	return -1;
}

int exbsgs(int a, int b, int p) {
	b %= p, a %= p;
	if(b == 1 || p == 1)return 0;
	int g = gcd(a, p), s = 0, c = 1;
	for (; g > 1; g = gcd(a, p)) {
		if (b % g != 0) return -1;
		b /= g, p /= g, (c *= a / g) %= p, s ++;
		if (b == c) return s;
	}
	int res = bsgs(a, b * Inv(c, p), p);
	return (~res ? res + s : res);
}

参考：OI Wiki，https://mancityfc.blog.luogu.org/solution-p3846，cqh’s blog 。