区区 1e8

大家好，我很喜欢 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 的代码量。

评测记录

CPP

#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"; 
	}
}

文章操作

相关推荐

评论

区区 1e8