P12541
lsj2009
·
·
题解
Preface
场上提出了 \mathcal{O}(\sqrt{n\log{n}}) 的做法，但是 system test 荣获 25pts/xk
Description
存在一个初始固定的正整数 n，可以进行若干次对交互库的询问，每次询问可以花费 |a| 的代价给出一个序列 a，交互库会返回 \sum\limits_{1\le i<j\le |a|} [a_i\equiv a_j\pmod{n}] 的值。
在花费不大于 1.1\times 10^5 的代价下确定 n 的值，n\le 10^9。
Solution
首先非常容易做到是判断一个数 x 是否是 n 的倍数：给出 a=\{1,x+1\} 即可。
则一个核心思想是，我们尝试找到 n 的一个倍数 n'，则 n 即为 n' 的所有因数中最小的为 n 倍数的数。则可对 n' 的每个质因数分别考虑他在 n 上的幂次，容易做到在不大于 2\log{n} 代价内求出 n 的值。
Sol 1
我的考场做法。
钦定一个阈值 B，先特判掉 n\le B 的情况（确定 n 直接二分，花费 B+B\log B 的代价）。
对于 n>B，我们尝试找到一个数 x>10^9 使得 x\bmod{n}\le B，则我们可以随 B'=\Omega{\left(\frac{n}{B}\right)} 个数（依据下面算法逻辑，其实还应保证该 B' 个数内没有冲突），此时期望下存在至少一个这样的 x，先对于 B' 个数二分确定数 x，再对于 B 个数二分确定 x\bmod{n} 的值，则 n'=x-(x\bmod{n})。
代价为 \mathcal{O}(B'+B\log{B'}+B)，取 B=\mathcal{O}\left(\sqrt{\frac{n}{\log{n}}}\right) 可以获得理论最优复杂度 \mathcal{O}(\sqrt{n\log{n}})，实际上应当可以获得还可以的分数，但是由于 pretest 和 system test 数据差异的存在以及 B' 所带的巨大常数，导致我只通过了 sub1,2 而在 sub3 上获得 0pts。
Sol 2
事实上 Sol 1 的思路是完全正确的，我们考虑进一步优化。暂且先不考虑 n\le B 的情况，我们发现复杂度里带个 \log 这导致我们代价难以很低，能否去掉？
不妨将问题刻画的更加形式化：
- 有集合 S_1,S_2，找到 x\in S_1,y\in S_2 使得 x \equiv y\pmod{n}。
考虑将 S_1 对半分为 S_1^L,S_1^R，将 S_2 对半分为 S_2^L,S_2^R，则进行如下询问：
-
询问 S_1\cup S_2^L。
-
如为真：询问 S_1^L\cup S_2^L。
-
如为假：询问 S_1^L\cup S_2^R。
则在 1.5|S_1|+|S_2| 代价下可将问题递归到规模为 \frac{1}{2} 的子问题。
则最终所花费代价为 3|S_1|+2|S_2|。
此时复杂度已经降为 \mathcal{O}(\sqrt{n})，但所带常数巨大，无法通过。
Sol 3
导致常数大的主要问题在于 S_2 集合的确定。
我们能不能不去 随 \Omega{\left(\frac{n}{B}\right)} 个数而找到一个集合使得其与 1,2,\cdots,B 间必然存在冲突？
令 m=10^9，给出集合：
注意到 x\in S_1=\{1,2,\cdots,B\},y\in S_2 组成的 y-x 遍历到了 [\frac{m}{2}+1,m] 内的所有数，而其中必有一 n 的倍数。
此时需 特判 S_{1/2} 内部存在冲突的情况。由于 B'\ge B，此时很好说明若 S_1 中存在冲突则 S_2 中必然存在冲突，故只需判断 S_2 内部是否有冲突并找到冲突的一对数即可。
类比 S_{1/2} 构造集合：
则 x\in S_3,y\in S_4 组成的 y-x 遍历到了所有的 kB,k\in[1,B']。
取 k_1=k_2=\sqrt{\frac{B'}{2}}，查询 S_3\cup S_4 即可判断 S_2 内部是否有冲突。若有冲突再花费 (k_1+k_2)^2=2B' 的代价确定冲突的 x,y 即可。
若无冲突，则再花费 3B+2B' 的代价确定 S_1,S_2 间的冲突即可。由基本不等式，总代价（对于判断 S_2 是否由冲突而产生的 2\sqrt{\frac{B'}{2}} 花费可以忽略）为 3B+2B'\ge 2\sqrt{6BB'}\ge2\sqrt{6\cdot\frac{m}{2}}=2\sqrt{3m}\approx 109545 可以接受。
不等号在 3B=2B'=\sqrt{3m} 时取等。