洛谷P3846 [TJOI2007] 可爱的质数/【模板】BSGS 题解

题目链接：P3846 [TJOI2007] 可爱的质数/【模板】BSGS

题意：

给定一个质数 $p$，以及一个整数 $a$，一个整数 $b$，现在要求你计算一个最小的非负整数 $k$，满足 $a^k \equiv b \pmod p$。

输入格式：

仅一行，有 $3$ 个整数，依次代表 $p, a, b$。

输出格式：

仅一行，如果有 $k$ 满足该要求，输出最小的 $k$，否则输出 no solution。

数据范围：

保证 $2\le a,b < p<2^{31}$。

BSGS 是求模质数 $p$​ 意义下的解，ExBSGS 是求模任意数下的解。

这里求的解实际上并不是模意义下的 $\log$ ，因为离散对数函数定义在 $a$ 为原根的情况下

BSGS 全称 Baby Step,Giant Step，可以用于解决形如以下高次同余方程，其中 $a,b,p$ 给出

$$a^x\equiv b \pmod{p}\\ x^a \equiv b \pmod{p}$$

第一行就是本题，而第二行实际上是 N 次剩余的板子题，虽说也可以用 BSGS 但是比较复杂。

因为 $a,p$ 显然互质，所以可以在模 $p$ 意义下做关于 $a$ 的乘除运算。

记 $t = \lfloor\sqrt{p}\rfloor$ ，设 $k = i\cdot t - j(0 \le j < t)$ ，则

$$a^{i\cdot t - j} \equiv b \pmod{p}$$

两侧同乘 $a^j$ 得

$$(a^{t})^i \equiv b \cdot a^j\pmod{p}$$

那么这有什么用呢？因为 $j$ 的取值仅有 $\mathcal{O}(\sqrt{p})$ ，所以同余式右侧的取值我们可以直接暴力算出来。

不妨把这些值存在一个哈希表内，然后枚举 $i \in [0,t]$ ，找左侧式子对应的值是否存在。

这样我们可以同时得到 $i,j$ ，又因为 $t$ 已知，所以 $k$ 就求出来了。

时间复杂度 $\mathcal{O}(\sqrt{p})$ ，听说能过 $p\le 10^{16}$ 。

代码：

// 2024年02月21日 17:33:40
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int P;
int qpow(int a, int b)
{
    int r = 1;
    while(b)
    {
        if(b & 1) r = r * a % P;
        b >>= 1; a = a * a % P;
    }
    return r;
}
map<int,int> mp;
int BSGS(int a, int b)
{
    int t = sqrt(P) + 1;
    for(int i = 0; i < t; i++) mp[b * qpow(a, i) % P] = i;
    a = qpow(a, t);
    if(!a) return (b == 0 ? 1 : -1);
    for(int i = 1; i <= t; i++)
    {
        int val = qpow(a, i);
        int j = mp.find(val) == mp.end() ? -1 : mp[val];
        if(j >= 0 && i * t - j >= 0) return i * t - j;
    }
    return -1;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int a,b; cin >> P >> a >> b;
    int res = BSGS(a,b);
    if(res == -1) cout << "no solution\n";
    else cout << res << '\n';
    return 0;
}