区区 1e8

Doqe · 2025-05-30 21:18:11 · 题解

大家好，我很喜欢 BSGS，所以我用 BSGS 过了这道题。

BSGS 的流程是，建立哈希表存储 g^{i}\quad(0\le i<B)，对于询问 x，枚举 j 直到 xg^{Bj}=g^{i}，即在哈希表内，那么区区小 t（x=g^t）就出来了。

其中预处理只需要区区 B 次，查询至多 \frac{qP}{B} 次。使用均值不等式得出 O(\sqrt{Pq}) 的复杂度，带个区区 2 的小常熟。计算一下区区 (2\times)2\times 10^7，区区 10^8 以内竟然过不去。

问题出在哈希表和乘法，区区乘法套路使用 Barret 即可。使用若干策略来降低哈希表常数：

• 首先注意到哈希表的数是 [0,P) 的整数，不妨使用 \frac P8 个字节开一个长度为 P 的 bitset，区区两百 MB。
  这样的好处是：我们每次询问真正只有一次访问大常数的哈希表。
  可以给块长 B 配点常数因子。
• 注意到 g^i 看起来非常随机的样子，我们宣称区区出题人完全防不了乱来。
  哈希表直接简单粗暴的对于后 x 位相同的键值开个 vector 存一下即可。 这样区区插入常数小到离谱，查找区区查找 q 次，常数多大都完全不慌。

本地跑一下发现随随便便进 2s，区区 0.5s。

接下来区区调参数，多次尝试并感受即可。于是使用 BSGS 通过了此题，并且只用了 1K + 区区 eps 的代码量。

评测记录

#include<bits/stdc++.h>
using namespace std;
int P,g,q,B;
struct Mod
{
    typedef long long LL;
    LL m, p;
    inline void init(int pp) { m = ((__int128)1 << 64) / pp; p = pp; }
    inline LL operator ()(LL x)
    {
        x -= ((__int128(x) * m) >> 64) * p;
        x>=P&&(x-=P);return x;
    }
} mod;
bitset<1000000009>Z;
const int U=1<<13; 
vector<pair<int,int>>ZZ[U];
inline void insert(int i,int v)
{
    if(Z[i])return;
    Z[i]=1;ZZ[i&U-1].emplace_back(i,v);
}
int main()
{
    cin.tie(0)->sync_with_stdio(0); 
    cin>>P>>g>>q;mod.init(P);
    B=max(sqrt(1ll*P*q)/3.56,1.0);
    int t=1;
    for(int i=0;i<B;++i)insert(t,i),t=mod(1ll*t*g);
    cerr<<clock()<<endl; 
    while(q--)
    {
        int w;cin>>w;
        w%=P;
        if(w%P==0)w=1;
        int z=0;
        while(1)
        {
            if(Z[w])
            {
                int Sw=0;
                for(auto k:ZZ[w&U-1])if(k.first==w){Sw=k.second;break;}
                z=((P-1ll)*2+Sw-z)%(P-1);
                break;
            }
            z+=B,w=mod(1ll*w*t);
        }
        cout<<z<<"\n"; 
    }
}