洛谷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;
}