题解：P12541 [APIO2025] Hack!

lichenghan · 2025-05-19 22:07:25 · 题解

我们先试图找到一个 n 的倍数 m。由于可以通过直接询问 \set{1,x+1} 来判定一个数 x 是否是 n 的倍数，所以已知 m 求 n 可以在 O(\log n) 的代价内完成。

有一个显然的性质：[5\times10^8,10^9] 中一定存在一个 n 的倍数。

于是考虑在这个区间内二分。考虑如何检查区间 [l,r] 内是否存在 n 的倍数。

取 b=\lfloor\sqrt{r-l+1}\rfloor。

考虑询问集合 S=\set{1,2,\cdots,b,b+l,2b+l,\cdots,\lfloor\frac{r-l}b\rfloor b+l,r+1}。

（放个代码可能好理解一些）

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\in[l,r]，一定存在 a,b\in S,|a-b|=x。

对于 a,b\in S，设 d=|a-b|，

可以发现，若 d\notin [l,r]，则 d\in[1,r-l+1]。

而若 [1,r-l+1] 中存在 n 的倍数，则 [l,r] 中必然存在 n 的倍数。

于是，S 中会发生哈希冲突等价于 [l,r] 中存在 n 的倍数。

这样，一次检查 [l,r] 的代价就是 2\sqrt{r-l+1}+O(1)。

记 N=10^9，总代价即为 O(\log N)+\sum_{i=2}^\infty2\sqrt{N\times 2^{-i}}，

化简得 \sqrt2(\sqrt2+1)\sqrt N + O(\log N)。实测总代价是 108000 左右。

题外话：作者赛时没有发现开头那个显然的性质，于是对着 [1,10^9] 二分，代价要乘上 \sqrt 2，78 分遗憾离场。