BSGS 模板

用于快速求方程 $a ^ x = b(p \in Primes)$ 的最小非负整数解。

查看代码

typedef long long LL;
int bsgs(int a, int b, int p)
{
    if (1 % p == b % p) return 0;
    int k = sqrt(p) + 1;
    unordered_map<int, int> H;
    for (int i = 0, j = b % p; i < k; i++, j = (LL)j * a % p) H[j] = i;
    int t = a;
    for (int i = 1; i < k; i++)
        t = (LL)t * a % p;
    for (int i = 1, j = t; i <= k; i++, j = (LL)j * t % p)
        if (H.count(j)) return (LL)i * k - H[j];
    return -1;
}

如果保证 $a$ 存在逆，那么方法可以拓展到矩阵上。

查看代码

const int N = 80;
typedef long long LL;
typedef array<array<int, N>, N> Matrix;
int n, p;
Matrix operator * (const Matrix &a, const Matrix &b)
{
    Matrix res;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            res[i][j] = 0;
            for (int k = 1; k <= n; ++k)
                res[i][j] = (res[i][j] + (LL)a[i][k] * b[k][j]) % p;
        }
    return res;
}
int BSGS (Matrix A, Matrix B)
{
    int k = sqrt(p) + 1;
    map <Matrix, int> H;
    Matrix s = B;
    for (int i = 0; i < k; ++i, s = s * A)
        H[s] = i;
    Matrix t = A;
    for (int i = 1; i < k; ++i)
        t = t * A;
    s = t;
    for (int i = 1; i <= k; ++i, s = s * t)
        if (H.count(s)) return i * k - H[s];
    return -1;
}