$$BSGS算法$$

$题目$

给定$a$,$b$,$p$,其中$p$为质数

求使 $a^x \equiv b (mod\ \ p)$ 成立的最小自然数 $x$

$分析$

由于$p$为质数,所以$a^p \equiv a(mod\ \ p)$(欧拉定理)

要使$x$最小,$x\in [0,p - 1]$

设$t = \left \lceil \sqrt{p} \right \rceil, i \in [1, t], j \in [1, t]$

则 $i * t - j \in [0, p - 1]$

即$a ^ {i * t - j} \equiv b (mod\ \ p)$

移项得$a^{i * t} \equiv b * a^j (mod \ \ p)$

先枚举$j\in [1, t]$, 计算所有$b * a^j \ \ mod \ \ p , 并放入哈希表中$

后枚举$i\in [1, t]$, 计算所有$a^{i * t} \ \ mod \ \ p, 并在哈希表中查询$

在存入时如果有冲突,由于要使$i*t-j$尽量小,用较大的$j$覆盖较小的$j$

时间复杂度$O(\sqrt{p})$

$Code$

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll bsgs(ll a, ll b, ll p)
{
    map<ll, ll> hash;
    ll t = sqrt(p) + 1, cur = 1, now = 1;
    for (ll j = 1; j <= t; j ++ )
    {
        cur = cur * a % p;
        hash[b * cur % p] = j;
    }
    for (ll i = 1; i <= t; i ++ )
    {
        now = now * cur % p;
        if (hash.count(now))return i * t - hash[now];
    }
    return -1;
}

int main()
{
    ll p, a, b;
    scanf("%lld%lld%lld", &p, &a, &b);
    ll ans = bsgs(a, b, p);
    if (ans == -1)puts("no solution");
    else printf("%lld", ans);
    return 0;
}