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

· · 题解

算法介绍

BSGS 算法用于求解离散对数问题，即：对于已知的三个数 b，n，p，找出最小的 l，使得 b^l \equiv n \pmod p。

首先由费马小定理，b^l \bmod p = b^{l \bmod (p-1)} \bmod p。所以，若满足条件的 l 存在，则 l_{\min} < p。

定义 s = \lceil \sqrt{p} \rceil，上取整是为了保证 s^2 \ge p，防止漏解。

设 l=xs-y (x,y < s)，则：

b^{xs-y} \equiv n \pmod p b^{xs} \equiv n b^y\pmod p

先从小到大枚举 y，用哈希表记录 nb^y \bmod p 对应的最大的 y 值（因为 y 越大，l 就越小），再从小到大枚举 x，在哈希表中查找 b^{xs} \bmod p，如果找到了，就说明 xs-y 是我们要的求的最小的 l。

正确性证明

设我们已经找到了一组 (x,y)，可知 b^{xs} \equiv n b^y\pmod p，由于 b 和 p 互质，所以 b^y 在模 p 意义下必有逆元，所以 b^{xs-y} \equiv n \pmod p，即 b^l \equiv n \pmod p，证毕。

这也是普通 BSGS 要求 b 和 p 必须互质的原因。

枚举 x 和枚举 y 都是 O(\sqrt p) 的，哈希表单次插入查询为 O(1)，所以总时间复杂度 O(\sqrt p)。

代码实现

这应该是非常短的一种实现了。有些人可能会写一个快速幂的函数，但是实际上没有必要，暴力计算 b^s 即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
unordered_map<ll, ll> mp;
ll p,b,n,s;
int main() {
    cin>>p>>b>>n, s=sqrt(p)+1;
    for(ll y=1, pw=n*b%p; y<=s; y++, pw=pw*b%p) mp[pw%p]=y;

    ll t=1;
    for(ll i=1; i<=s; i++) t=t*b%p;
    for(ll x=1, pw=t; x<=s; x++, pw=pw*t%p)
        if(mp[pw])
            return cout<<x*s-mp[pw], 0;

    cout<<"no solution";
    return 0;
}