专栏文章

P12541

llsj2009Isj2OO9
P12541题解参与者 6已保存评论 5

文章操作

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

当前评论
5 条
当前快照
1 份
快照标识符
@mip979t1
此快照首次捕获于
2025/12/03 08:13
3 个月前
此快照最后确认于
2025/12/03 08:13
3 个月前
查看原文

Preface

场上提出了 O(nlog⁡n)\mathcal{O}(\sqrt{n\log{n}}) 的做法，但是 system test 荣获 25pts/xk

Description

存在一个初始固定的正整数 nn，可以进行若干次对交互库的询问，每次询问可以花费 ∣a∣|a| 的代价给出一个序列 aa，交互库会返回 ∑1≤i<j≤∣a∣[ai≡aj(modn)]\sum\limits_{1\le i<j\le |a|} [a_i\equiv a_j\pmod{n}] 的值。
在花费不大于 1.1×1051.1\times 10^5 的代价下确定 nn 的值，n≤109n\le 10^9。

Solution

首先非常容易做到是判断一个数 xx 是否是 nn 的倍数：给出 a={1,x+1}a=\{1,x+1\} 即可。
则一个核心思想是，我们尝试找到 nn 的一个倍数 n′n'，则 nn 即为 n′n' 的所有因数中最小的为 nn 倍数的数。则可对 n′n' 的每个质因数分别考虑他在 nn 上的幂次，容易做到在不大于 2log⁡n2\log{n} 代价内求出 nn 的值。

Sol 1

我的考场做法。
钦定一个阈值 BB，先特判掉 n≤Bn\le B 的情况（确定 nn 直接二分，花费 B+Blog⁡BB+B\log B 的代价）。
对于 n>Bn>B，我们尝试找到一个数 x>109x>10^9 使得 x mod n≤Bx\bmod{n}\le B，则我们可以随 B′=Ω(nB)B'=\Omega{\left(\frac{n}{B}\right)} 个数（依据下面算法逻辑，其实还应保证该 B′B' 个数内没有冲突），此时期望下存在至少一个这样的 xx，先对于 B′B' 个数二分确定数 xx，再对于 BB 个数二分确定 x mod nx\bmod{n} 的值，则 n′=x−(x mod n)n'=x-(x\bmod{n})。
代价为 O(B′+Blog⁡B′+B)\mathcal{O}(B'+B\log{B'}+B)，取 B=O(nlog⁡n)B=\mathcal{O}\left(\sqrt{\frac{n}{\log{n}}}\right) 可以获得理论最优复杂度 O(nlog⁡n)\mathcal{O}(\sqrt{n\log{n}})，实际上应当可以获得还可以的分数，但是由于 pretest 和 system test 数据差异的存在以及 B′B' 所带的巨大常数，导致我只通过了 sub1,2 而在 sub3 上获得 0pts。

Sol 2

事实上 Sol 1 的思路是完全正确的，我们考虑进一步优化。暂且先不考虑 n≤Bn\le B 的情况，我们发现复杂度里带个 log⁡\log 这导致我们代价难以很低，能否去掉？
不妨将问题刻画的更加形式化：
  • 有集合 S1,S2S_1,S_2，找到 x∈S1,y∈S2x\in S_1,y\in S_2 使得 x≡y(modn)x \equiv y\pmod{n}。
考虑将 S1S_1 对半分为 S1L,S1RS_1^L,S_1^R，将 S2S_2 对半分为 S2L,S2RS_2^L,S_2^R，则进行如下询问：
  • 询问 S1∪S2LS_1\cup S_2^L。
    • 如为真：询问 S1L∪S2LS_1^L\cup S_2^L。
    • 如为假：询问 S1L∪S2RS_1^L\cup S_2^R。
则在 1.5∣S1∣+∣S2∣1.5|S_1|+|S_2| 代价下可将问题递归到规模为 12\frac{1}{2} 的子问题。
则最终所花费代价为 3∣S1∣+2∣S2∣3|S_1|+2|S_2|。
此时复杂度已经降为 O(n)\mathcal{O}(\sqrt{n})，但所带常数巨大，无法通过。

Sol 3

导致常数大的主要问题在于 S2S_2 集合的确定。
我们能不能不去 随 Ω(nB)\Omega{\left(\frac{n}{B}\right)} 个数而找到一个集合使得其与 1,2,⋯ ,B1,2,\cdots,B 间必然存在冲突？
令 m=109m=10^9，给出集合：
  • S2={m2+1+B,m2+1+2B,⋯ ,m2+1+B′B}S_2=\{\frac{m}{2}+1+B,\frac{m}{2}+1+2B,\cdots,\frac{m}{2}+1+B'B\}，其中 B′B≥m2,B′≥BB'B\ge \frac{m}{2},B'\ge B。
注意到 x∈S1={1,2,⋯ ,B},y∈S2x\in S_1=\{1,2,\cdots,B\},y\in S_2 组成的 y−xy-x 遍历到了 [m2+1,m][\frac{m}{2}+1,m] 内的所有数，而其中必有一 nn 的倍数。
此时需 特判 S1/2S_{1/2} 内部存在冲突的情况。由于 B′≥BB'\ge B，此时很好说明若 S1S_1 中存在冲突则 S2S_2 中必然存在冲突，故只需判断 S2S_2 内部是否有冲突并找到冲突的一对数即可。
类比 S1/2S_{1/2} 构造集合：
  • S3={B,2B,⋯ ,k1B}S_3=\{B,2B,\cdots,k_1B\}。
  • S4={BB′2+B+k1B,⋯ ,BB′2+B+k2k1B}S_4=\{\frac{BB'}{2}+B+k_1B,\cdots,\frac{BB'}{2}+B+k_2k_1B\}。有 k1k2≥B′2k_1k_2\ge \frac{B'}{2}。
则 x∈S3,y∈S4x\in S_3,y\in S_4 组成的 y−xy-x 遍历到了所有的 kB,k∈[1,B′]kB,k\in[1,B']。
取 k1=k2=B′2k_1=k_2=\sqrt{\frac{B'}{2}}，查询 S3∪S4S_3\cup S_4 即可判断 S2S_2 内部是否有冲突。若有冲突再花费 (k1+k2)2=2B′(k_1+k_2)^2=2B' 的代价确定冲突的 x,yx,y 即可。
若无冲突，则再花费 3B+2B′3B+2B' 的代价确定 S1,S2S_1,S_2 间的冲突即可。由基本不等式，总代价（对于判断 S2S_2 是否由冲突而产生的 2B′22\sqrt{\frac{B'}{2}} 花费可以忽略）为 3B+2B′≥26BB′≥26⋅m2=23m≈1095453B+2B'\ge 2\sqrt{6BB'}\ge2\sqrt{6\cdot\frac{m}{2}}=2\sqrt{3m}\approx 109545 可以接受。
不等号在 3B=2B′=3m3B=2B'=\sqrt{3m} 时取等。

评论

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

正在加载评论...