P11175 【模板】基于值域预处理的快速离散对数

Genius_Star · 2025-12-03 18:00:51 · 题解

思路：

根据题意，考虑对值域进行预处理。

如果预处理 0 \sim n 的 \log 的值，考虑 \log 本身的性质与原根的性质，必然有 \log(ab) = \log a + \log b，于是可以想到线性筛来处理；只需要对所有素数求出其的 \log 值。

素数分布在 1 \sim n 内大概有 \frac{n}{\log n} 个；即在朴素的 BSGS 基础上，进行 q = \frac{n}{\log n} 查询；与 P12239 [蓝桥杯 2023 国 Java A] 游戏的得分 题目类似，可以改变朴素 BSGS 的阈值分治大小 B 来平衡复杂度，取 B = \sqrt{qp}，可以使总时间复杂度降到 O(\sqrt{pq} = \sqrt{\frac{np}{\log n}})。

同样根号分治，然后考虑预处理 1 \sim \sqrt{p} + 1 的 \log 值，时间复杂度是 O(\frac{p^{\frac{3}{4}}}{\log^{\frac{1}{2}} p})。

那么对于 x > \sqrt{p} + 1，设 p = xq + r, r \in [0, x)，那么显然有 q \le \sqrt{p}，那么我们是知道 \log q 的值的，于是有（注意式子中是对 p 取模的）：

此时可以递归到子问题 \log r 处解决，但是这样最坏还是线性的，考虑怎么递归到 \log(x - r)，此时每次就最少减半，就是 \log 次的；考虑 p = xq + r，两边再加一个 x，得到 p + x = x(q + 1) + r，于是：

显然此时 \log(q + 1) 也是预处理出来了的。

于是单次询问复杂度是 \log p。

总复杂度为 O(\frac{p^{\frac{3}{4}}}{\log^{\frac{1}{2}} p} + q \log p)。

完整代码：

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#define lowbit(x) x & (-x)
#define pi pair<ll, ll>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 4e4 + 10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
            f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
int p, g, q, x;
namespace Quick_BSGS{
    int p, g, pp, h, _lg1, m, cnt, B;
    int lg[N], prime[N];
    bool vis[N];
    gp_hash_table<int, int> mp;
    inline int qpow(int a, int b, int mod){
        int ans = 1;
        while(b){
            if(b & 1)
                ans = 1ll * ans * a % mod;
            a = 1ll * a * a % mod;
            b >>= 1;
        }
        return ans;
    }
    inline int ask(int b){
        if(b == 1)
            return 0;
        b = qpow(b, p - 2, p);
        int now = b;
        for(int i = 1; i <= (p / B) + 1; ++i){
            now = 1ll * now * h % p;
            if(mp.find(now) != mp.end())
                return i * B - mp[now];
        }
        return -1;
    }
    inline void init(int _p, int _g){
        p = _p, g = _g;
        pp = p - 1;
        B = sqrt(p * sqrt(p) / log(sqrt(p)));
        int now = 1;
        for(int i = 0; i < B; ++i){
            mp[now] = i;
            now = 1ll * now * g % p;
        }
        h = now;
        _lg1 = ask(p - 1);
        m = sqrt(p) + 1;
        lg[1] = ask(1);
        for(int i = 2; i <= m; ++i){
            if(!vis[i]){
                prime[++cnt] = i;
                lg[i] = ask(i);
            }
            for(int j = 1; j <= cnt && i * prime[j] <= m; ++j){
                vis[i * prime[j]] = 1;
                lg[i * prime[j]] = (lg[i] + lg[prime[j]]) % pp;
                if(i % prime[j] == 0)
                  break;
            }
        }
//      for(int i = 1; i <= 10; ++i){
//          cerr << i << ' ' << lg[i] << ' ' << qpow(g, lg[i], p) << '\n';
//      }
//      putchar('\n');
    }
    inline int query(int x){
        if(x <= m)
          return lg[x];
        int r = p % x, q = (p - r) / x;
        if(r <= x - r)
          return ((_lg1 + query(r)) % pp - lg[q] + pp) % pp;
        return (query(x - r) - lg[q + 1] + pp) % pp;
    }
};
int main(){
    p = read(), g = read();
    Quick_BSGS::init(p, g);
    q = read();
    while(q--){
        x = read();
        write(Quick_BSGS::query(x));
        putchar('\n');
    }
    return 0;
}