专栏文章

题解：P12541 [APIO2025] Hack!

llichenghan
P12541题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip92670
此快照首次捕获于
2025/12/03 08:09
3 个月前
此快照最后确认于
2025/12/03 08:09
3 个月前
查看原文
我们先试图找到一个 nn 的倍数 mm。由于可以通过直接询问 { 1,x+1 }\set{1,x+1} 来判定一个数 xx 是否是 nn 的倍数，所以已知 mm 求 nn 可以在 O(log⁡n)O(\log n) 的代价内完成。
有一个显然的性质：[5×108,109][5\times10^8,10^9] 中一定存在一个 nn 的倍数。
于是考虑在这个区间内二分。考虑如何检查区间 [l,r][l,r] 内是否存在 nn 的倍数。
取 b=⌊r−l+1⌋b=\lfloor\sqrt{r-l+1}\rfloor。
考虑询问集合 S={ 1,2,⋯ ,b,b+l,2b+l,⋯ ,⌊r−lb⌋b+l,r+1 }S=\set{1,2,\cdots,b,b+l,2b+l,\cdots,\lfloor\frac{r-l}b\rfloor b+l,r+1}。
（放个代码可能好理解一些）
CPP
bool chk(int l,int r){
	int b=sqrt(r-l+1);
	vector<int> a;
	for(int i=1;i<=b;i++) a.push_back(i);
	for(int i=b+l;i<r+1;i+=b) a.push_back(i);
	a.push_back(r+1);
	return collisions(a);
}
正确性证明：
显然对于所有 x∈[l,r]x\in[l,r]，一定存在 a,b∈S,∣a−b∣=xa,b\in S,|a-b|=x。
对于 a,b∈Sa,b\in S，设 d=∣a−b∣d=|a-b|，
可以发现，若 d∉[l,r]d\notin [l,r]，则 d∈[1,r−l+1]d\in[1,r-l+1]。
而若 [1,r−l+1][1,r-l+1] 中存在 nn 的倍数，则 [l,r][l,r] 中必然存在 nn 的倍数。
于是，SS 中会发生哈希冲突等价于 [l,r][l,r] 中存在 nn 的倍数。
这样，一次检查 [l,r][l,r] 的代价就是 2r−l+1+O(1)2\sqrt{r-l+1}+O(1)。
记 N=109N=10^9，总代价即为 O(log⁡N)+∑i=2∞2N×2−iO(\log N)+\sum_{i=2}^\infty2\sqrt{N\times 2^{-i}}，
化简得 2(2+1)N+O(log⁡N)\sqrt2(\sqrt2+1)\sqrt N + O(\log N)。实测总代价是 108000108000 左右。
题外话：作者赛时没有发现开头那个显然的性质，于是对着 [1,109][1,10^9] 二分，代价要乘上 2\sqrt 2，7878 分遗憾离场。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...