BSGS 算法模板题

有\(a^{x} \equiv b (mod \; p)\)，求\(x\)的值。我们可以来推下这个式子，首先，这个\(x \in [0, p]\)，我们可以设\(x=im-j\)，其中\(m=\lceil \sqrt{p} \rceil\)。显然，\(j \in [0, m], i \in [1, m]\)。式子变成这个样子：

\[a^{im}\equiv a^j b (mod \; p)\]

然后我们只需要求出后半部分，压入 map 中，再枚举前半部分即可求出。

代码

// P3846.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll p, a, b;
ll quick_power(ll base, ll tim)
{
    ll tmp = 1;
    while (tim)
    {
        if (tim & 1)
            tmp = tmp * base % p;
        base = base * base % p;
        tim >>= 1;
    }
    return tmp;
}
map<ll, ll> hashTable;
int main()
{
    scanf("%lld%lld%lld", &p, &a, &b);
    a %= p;
    if (a == 0)
    {
        if (b == 0)
            printf("0");
        else
            printf("no solution");
        return 0;
    }
    hashTable.clear();
    ll m = ceil(sqrt(p));
    for (int j = 0, x = 1; j <= m; j++, x = x * a % p)
        hashTable[x * b % p] = j;
    ll unit = quick_power(a, m);
    for (int i = 1, x = unit; i <= m; i++, x = x * unit % p)
        if (hashTable.count(x))
        {
            printf("%lld", i * m - hashTable[x]);
            return 0;
        }
    printf("no solution");
    return 0;
}