Extended-BSGS

同步发表于 P4195 题解。

0. 前置知识 & 废话

逆元。

我的逆元 Blog

1. 普通版 BSGS

要求 $\gcd(a,p)=1$。

其实就是一个分块的思想。

设 $t=\lceil\sqrt p\rceil$，我们可以将每一个答案 $x=i\times t-m$，其中 $i,m\leq t$。

$a^{i\cdot t-m}=b\pmod p\Leftrightarrow a^{i\cdot t}=b\times a^{m}\pmod p$。

我们枚举每一个 $i$，怎么找到右边的呢？

其实，我们可以先将 $b\times a^m$ 全部用 Hash 存下来。

这样就可以直接查找了。

2. 扩展版 BSGS

想办法解决问题，我们应该实现 $\gcd(a,p)=1$。

首先，同余具有一条性质：

$$a=b\pmod c (\gcd(a,c)=1)\Leftrightarrow a\times d=b\times d\pmod {c\times d}$$

可以感性的理解一下 （主要是不会证）。

那么，我们就可以执行消除因子。

每次在两边除以 $d=\gcd(a,p)$。

$$a^x=b\pmod p\Rightarrow \dfrac{a}{d}\times a^{x-1}=\dfrac{b}{d}\pmod {\dfrac{p}{d}}$$

重复执行该语段，直到 $\gcd(a,p)=1$ 为止。

将所有的 $\dfrac{a}{d}$ 都乘起来，记为 $tot$。

假设执行了 $cnt$ 次，则原问题转化为 $tot\times a^{x-cnt}=b\pmod p\Leftrightarrow a^{x-cnt}=b\times tot^{-1}\pmod p$

注意，这里有一些细节：

1. 如果 $b$ 不被 $d$ 整除，则直接返回无解。
2. 答案可能小于 $cnt$，我们必须枚举 $[0,cnt-1]$ 的解，看有没有。

于是就转化为了普通的 BSGS 了。

using LL = long long;

int Mod;

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

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

inline int& adj(int &x) { return x += x >> 31 & Mod; }

int qpow(int a, int k)
{
	int res = 1;
	for (; k; k >>= 1, a = (LL) a * a % Mod)
		(k & 1) && (res = (LL) res * a % Mod);
	return res;
}

int ExBSGS(int a, int b)
{
	a %= Mod, b %= Mod;
	if (b == 1 || Mod == 1) return 0;
	if (!a) return b ? -1 : 1;
	int t, cur = 1, g = 0;
	while ((t = Gcd(a, Mod)) != 1)
	{
		if (b % t) return -1;
		++ g, b /= t, Mod /= t, cur = (LL) cur * (a / t) % Mod;
		if (cur == b) return g;
	}
	std::map<int, int> mp;
	int B = std::sqrt(Mod) + 1;
	LL x, y;
	ExGcd(cur, Mod, x, y), x = (x % Mod + Mod) % Mod;
	cur = (LL) x * b % Mod;
	mp[cur] = 0;
	for (int i = 1; i <= B; ++ i) mp[cur = (LL) cur * a % Mod] = i;
	int pw = qpow(a, B);
	cur = 1;
	for (int i = 1; i <= B; ++ i)
		if (mp.count(cur = (LL) cur * pw % Mod))
			return i * B - mp[cur] + g;
	return -1;
}

int main()
{
    int a, b;
    while (read(a, Mod, b), a || b || Mod)
    {
        int res = ExBSGS(a, b);
        if (~res) write(res, '\n');
        else write("No Solution\n");
    }
    return 0;
}