数论：Extended-BSGS

· · 题解

Update on 2021-11-01： 更新了代码，可能会提升阅读效果吧。

Update on 2022-07-04： 被 @RainFestival Hack 了，更新了代码，已经可以通过。

0. 前置知识 & 废话

逆元。

我的逆元 Blog

1. 普通版 BSGS

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

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

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

我们枚举每一个 $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;
}