BSGS(Baby Step Giant Step)及其扩展

P3846 [TJOI2007] 可爱的质数/【模板】BSGS

###BSGS

首先了解一下BSGS是用来干什么的,我们知道,扩展欧几里得算法可以用来解线性同余方程,那么像 $a^t\equiv b(mod~p)(gcd(a,p)=1)$ 这样的方程,就是用BSGS来解决的

根据欧拉定理 $a^c\equiv a^{c~mod~\phi(m)}gcd(a,m)=1$ 可以知道 $t$ 是每 $\phi(p)$ 次一循环,所以只需要枚举 $0$~$phi(p)-1$ 就行了,不妨直接枚举 $p$

可以把 $p$ 划分成长度为 $k=\sqrt{p}+1$ 的若干块,也可以大于这个长度,令 $t=kx-y,x\in[1,k],y\in[0,k-1]$,这样就能枚举到所有的值了

$$\Rightarrow a^{kx}\equiv b\times a^y(mod~p)$$

直接通过分块处理即可,然后预处理出所有的 $b\times a^y$ 的值对应的 $y$,在枚举 $x$ 时直接查询是否存在对应的 $y$ 使得 $a^{kx}\equiv b\times a^y$ 即可,时间复杂度 $O(\sqrt{n})$

注意先特判0,因为0有可能会被其它的 $y$ 覆盖

结合代码

#include<iostream>
#include<cstdio>
#include<unordered_map>
#include<cmath>
using namespace std;
typedef long long ll;

int BSGS(int a, int p, int b)
{
    if (1 % p == b % p)
        return 0;
    unordered_map<int, int> hash;
    int k = sqrt(p) + 1;
    for (int i = 0, j = b % p; i < k; i++, j = (ll)j * a % p)
        hash[j] = i;
    int ak = 1;
    for (int i = 1; i <= k; i++)
        ak = (ll)ak * a % p;
    for (int i = 1, j = ak; i <= k; i++, j = (ll)ak * j % p)
        if (hash.count(j))
            return i * k - hash[j];
    return -1;
}

int main()
{
    int a, p, b;
    scanf("%d%d%d", &p, &a, &b);
    int res = BSGS(a, p, b);
    if (res == -1)
        printf("no solution\n");
    else
        printf("%d\n", res);
    return 0;
}

###exBSGS

P4195 【模板】扩展BSGS

相比于朴素版的BSGS,exBSGS不一定满足 $gcd(a,p)=1$

可以分类讨论一下,同样先特判0

1.$gcd(a,p)=1$,直接调用朴素版BSGS

2.$gcd(a,p)\ne 1$

令 $d=gcd(a,p)$

将方程转化一下 $\Rightarrow a^t+kp=b$

显然若 $gcd(b,d)=1$,则无解

反正 $\Rightarrow \frac{a}{d}\times a^{t-1}\equiv\frac{b}{d}(mod~\frac{p}{d}) \Rightarrow a^{t-1}\equiv\frac{b}{d}\times(\frac{a}{d})^{-1}(mod~\frac{p}{d})$

这样我们就有构造出了一个新的方程,一直递归下去,直到 $gcd(a,p)=1$

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<unordered_map>
#define INF (1e8)
using namespace std;
typedef long long ll;

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

int BSGS(int a, int p, int b)
{
    if (1 % p == b % p)
        return 0;
    unordered_map<int, int> hash;
    int k = sqrt(p) + 1;
    for (int i = 0, j = b % p; i < k; i++, j = (ll)j * a % p)
        hash[j] = i;
    int ak = 1;
    for (int i = 1; i <= k; i++)
        ak = (ll)ak * a % p;
    for (int i = 1, j = ak % p; i <= k; i++, j = (ll)j * ak % p)
        if (hash.count(j))
            return i * k - hash[j];
    return -INF;
}

int exBSGS(int a, int p, int b)
{
    b = (b % p + p) % p;
    if (1 % p == b % p)
        return 0;
    int x, y;
    int d = exgcd(a, p, x, y);
    if (d > 1)
    {
        if (b % d)
            return -INF;
        exgcd(a / d, p / d, x, y);
        return exBSGS(a, p / d, (ll)b / d * x % (p / d)) + 1;
    }
    return BSGS(a, p, b);
}

int main()
{
    int a, p, b;
    while (scanf("%d%d%d", &a, &p, &b) && (a || p || b))
    {
        int res = exBSGS(a, p, b);
        if (res == -INF)
            printf("No Solution\n");
        else
            printf("%d\n", res);
    }
    return 0;
}