高次同余方程 $BSGS$

第一篇(Blog)...

还是决定把(luogu)上的那篇搬过来了。

---

BSGS，又名北上广深

它可以用来求(a^x equiv b (mod n))这个同余方程的一个解，其中(a,n)互质。

欧拉定理告诉我们，这里(a^{varphi(n)} equiv 1 (mod n))

由于(a^0 equiv 1 (mod n))，所以这里(x)到(varphi(n))后(a^x mod n)就开始循环了。

所以我们最坏情况就是(n)为素数时，从(0)到(n-1)枚举(x)就行了。

这样我们就得到了一个(O(n))复杂度的优秀算法。

然而(n < 2^{31})......

我们考虑让(x = im - j(0 le j le m))，即把(0...n-1)这(n)个数按每块大小为(m)分块。

就有

[a^{im - j} equiv b (mod n) ]

两边同时乘(a^j)得

[a^{im} equiv ba^j (mod n) ]

对于等式右边，总共只会有(m+1)种不同的(j)，我们把(ba^0,ba^1,...,ba^m)全塞到一个(map)里,(i)也只会有(lceil frac{n}{m} ceil)种取值，直接暴力。

最后复杂度为(O(m + lceilfrac{n}{m} ceil))

取(m = lceil sqrt{n} ceil)，就可以做到(O(sqrt{n}))

当然，用(map)的话还要乘上一个(log)。

其实分块的时候(j)取到(m)可能会导致有些(x)被考虑到两次，但并不影响，而且边界还不怎么需要处理。

贴一下Luogu P3846(板子题)的代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int fpow(int a, int b, int c){
	int ret = 1;
	for (a %= c; b; b>>=1, a = 1ll*a*a % c) if (b&1) ret = 1ll * ret * a % c;
	return ret;
}

int BSGS(int a, int b, int n, int &ret) {
	int m = ceil(sqrt(n));
	map<int,int> h;
	for (int i = 0, tmp = b%n; i <= m; i++, tmp = 1ll*tmp*a%n)
		h[tmp] = i;
	a = fpow(a, m, n);
	for (int tmp = a, i = 1; i <= m; i++, tmp = 1ll*tmp*a%n)
		if (h.count(tmp)) { ret = 1ll*i*m - h[tmp]; return 1; }
	return 0;
}

int main(){
	int a, b, n, flg, ans; scanf("%d%d%d", &n, &a, &b);
	flg = BSGS(a, b, n, ans);
	if (!flg) puts("no solution"); else printf("%d
", ans);
	return 0;
}

---

还有比较毒瘤的就是如果(a equiv 0 (mod n))的时候，需要特判(b otequiv 0 (mod n))

因为如果(a)是(n)的倍数，那怎么乘都是(0)...

所以板子在这里：

int BSGS(int a, int b, int n, int &ret) {
	a %= n, b %= n;
	if (a == 0) { if (b == 0) { ret = 0; return 1; } else return 0; }
	int m = ceil(sqrt(n)); map<int,int> h;
	for (int tmp = b%n, i = 0; i <= m; i++, tmp = 1ll*tmp*a % n) h[tmp] = i;
	a = fpow(a, m, n);
	for (int tmp = a%n, i = 1; i <= m; i++, tmp = 1ll*tmp*a % n)
		if (h.count(tmp)) { ret = 1ll*i*m - h[tmp]; return 1; }
	return 0;
}

---

(ExBSGS)的话。。。改天学吧 感觉也没什么用