当前位置：首页 > news >正文

[luogu12541] [APIO2025] Hack! - 交互 - 构造 - 数论 - BSGS

news 来源：原创 2025/7/17 16:35:20

传送门：https://www.luogu.com.cn/problem/P12541

题目大意：有一个数 $n$ ，你不知道是多少；你每次可以向交互库询问一个正整数集合 $A$ （其中元素互不相同），交互库返回：将集合中的数对 $n$ 取模后，有多少对数是相同的。也就是 $\sum_{1 \le i < j \le |A|}[A_i \equiv A_j \pmod n]$ 。你要通过若干次询问求出 $n$ 。

数据范围： $\ne 10^9$ ，询问的开销是集合大小，要求总开销不超过 $110000$ 。

前两档部分分的做法很多，我们直接跳过部分分来看正解。

首先考虑这样一件事：假设我们得到了某一对数 $(x, y)$ 是冲突的，这意味着什么？

两数冲突意味着两数对 $n$ 取模的值相同，也就是说两数之差是 $n$ 的倍数，换句话说 $n$ 一定是两数之差 $w = ∣ x - y ∣$ 的因数。

因此我们只需要直接检查所有 $w$ 的因子即可，比较聪明的检查方法是考虑质因数分解 $w=\prod_i p_i^{c_i}$ ，然后对每个指数 $c_i$ 进行二分。这一部分的开销显然是很小的，所以我们只需要设法找到一对冲突的 $(x, y)$ 即可。

现在假设我们已经得到了一个存在冲突的集合 $A$ ，如何从中具体找到哪两个数冲突？这里就要用到这类交互题常见的二分技巧：

将集合 $A$ 划分为两个子集 $S, T$ ，分别对每个子集单独检验。如果某个子集内部已经有冲突了，就把问题规模缩小了一半；否则冲突一定发生在 $S$ 和 $T$ 之间。
再将 $S, T$ 分别划分为 $S_1, S_2, T_1, T_2$ ，然后先查询 $S_1\cup T$ ，如果有冲突就保留 $S_1$ ，否则保留 $S_2$ ；再查询 $S_*\cup T_1$ （ $S_*$ 是上一步中保留的部分）如果有冲突就保留 $T_1$ ，否则保留 $T_2$ 。
这样通过两次查询就将 $S$ 和 $T$ 的规模都缩小了一半，开销为 $∣ S ∣ + 1.5∣ T ∣$ 。基于等比数列求和可知，整个二分过程的总开销为 $2∣ S ∣ + 3∣ T ∣$ 。但请注意这没有包含最开始检验 $A$ 集合存在冲突，以及检验 $S$ 和 $T$ 内部是否有冲突的开销；如果 $S$ 或 $T$ 内部确实存在冲突，得到的总开销将有所减小。

总之，花费 $O (∣ A ∣)$ 的开销就可以找到一对冲突的数。设 $N=10^9$ 为 $n$ 的最大范围，根据题目允许的查询开销，我们需要找到一个大小约为 $O(\sqrt{N})$ 且存在冲突的初始集合 $A$ 。

一种容易想到的方案是基于生日悖论：随机选取 $\Theta(\sqrt{n})$ 个 $1\sim n$ 范围内的数，则有较大概率会出现相同的数。这里我们可以直接在 $10^{18}$ 范围内随机选取一组数，那么它们对 $n$ 取模的值也大致是在 $0\sim n-1$ 范围内均匀随机的，当集合足够大时就很有可能出现冲突。

但由于要精确分析总开销，需要合理估计使用的集合大小。设 $|A|=c\sqrt{N}$ ，则可以不严谨地估计出没有发生冲突的概率大约为 $(\frac{1}{e})^\frac{c^2}{2}$ 。考虑到评分规则看的是最坏情况，一种方案是选一个较小的 $c$ ，然后如果没有冲突就重新随机；或者是选一个足够大的 $c$ 然后自信宣称里面一定存在冲突，直接免去检查 $A$ 这一步（OI 赛制下会比较冒险）。但无论如何整个过程都比较看脸，最终得到的最大开销大约会在 $4\times10^5$ 这个级别，只能获得不超过 $50$ 分。

如何做到更优？我们希望免去这样的随机，直接得到一个确定性的存在冲突的集合 $A$ ；更进一步如果能直接给出 $S$ 和 $T$ ，使得它们各自内部没有冲突（或很容易检验）而二者之间一定存在冲突，就可以再减少一步检验的开销，只剩下 $2∣ S ∣ + 3∣ T ∣$ 的二分开销。

容易看出，我们实际上只需要让每个 $i\in \{1,...,N\}$ ，都存在 $s\in S, t \in T$ 使得 $∣ s - t ∣ = i$ 即可。更进一步可以把上述 $i$ 的范围改成 $\{\frac{N}{2} + 1,...,N\}$ 即可，因为不超过 $\frac{N}{2}$ 的数的某个倍数一定都涵盖在内了。

熟悉数论的小伙伴可能已经想到，数论中的大步小步（BSGS）算法本质上就是在做类似的事。具体而言，构造 $S=\{1,2,...,p\}, T=\{\frac{N}{2}+p,\frac{N}{2}+2p,...,\frac{N}{2}+pq\}$ ，满足 $\frac{N}{2}$ 即可。容易验证这样的构造满足要求。

然后如何检查 $S$ 和 $T$ 各自内部是否有冲突？注意到 $S$ 和 $T$ 都是等差数列，其实就是相当于把问题转化成了“查询 $n$ 是否不超过某个 $N^{'}$ ”的子问题，只不过这个 $N^{'}$ 比原问题要小得多，只有 $O(\sqrt{N})$ 级别。我们可以再套一层 BSGS 来解决：以检查 $S$ 为例，直接查询 $\{1,2,...,p', \frac{p}{2} + p', \frac{p}{2} + 2p', ..., \frac{p}{2} + p'q'\}$ 即可，至于 $T$ 其实就是把检查的数整体放大 $p$ 倍而已。

如果 $S$ 和 $T$ 内部没有冲突，按照之前的二分流程跑就行；如果有冲突，考虑到 $S$ 和 $T$ 都不大且呈等差数列，可以直接按类似 ${1,2\}, \{1,3\}, ..., \{1,p\}$ 检查过去，开销比无冲突时正常做二分的流程小得多，就不考虑了。

分析一下目前的总开销：首先是二分的主流程，需要确定 $p, q$ 的大小，使得 $pq>5\times 10^8$ ，开销为 $2 p + 3 q$ ；然后是对 $S$ 和 $T$ 内部的开销，只需要取 $p'=q'=\sqrt\frac{p}{2}$ （或 $\sqrt\frac{q}{2}$ ），这一步的开销是 $2\sqrt\frac{p}{2}+2\sqrt\frac{q}{2}$ 。

最后是得到一对冲突的数之后检查因子的开销：每次检查因子 $w^{'}$ 其实就是查询 ${1, w'+1\}$ ，而 $10^9$ 范围内检查因子的总开销最大的数是 $901800900=2^2\times 3^2\times 5^2\times 7^2\times 11^2\times 13^2$ ，总开销为 $24$ 。

写一个程序精确计算一下，发现当 $p = 27512, q = 18174$ 时，理论最大总开销……竟然刚好是精确的 $110000$ ！当然实际上这是在每次对于奇数的二分都恰好往大的一侧递归，且最终得到的 $w$ 又刚好达到二分质因子的最大开销时才会发生，实际上不会同时达到，实测结果是在在 $n = 768398400$ 时会达到最大值 $109996$ 。

当然有一个小优化可以让它变得不是那么紧：考虑二分时交换 $S$ 和 $T$ 集合的地位，这样开销就变成了 $3 p + 2 q$ ，这样算出来的 $q$ 会比 $p$ 大。再结合 $S$ 和 $T$ 本身的构造方式，容易发现每一个 $S$ 中可能出现的两数之差，其倍数都出现在 $T$ 中了。因此我们可以只对 $T$ 集合进行检验。此时的精确结果为将上述 $p$ 和 $q$ 颠倒，理论次数上界为 $109809$ ，实际最大为 $109805$ 。

注意到上述做法实际上只利用了“集合有没有冲突”而没有利用“具体有多少对冲突”的信息，或许有办法利用这一信息进一步优化。你有更优的做法吗？欢迎讨论~

#include <bits/stdc++.h>
using namespace std;
#define li long long
#define vl vector<li>
#define pb push_back
#define pii pair<int,int>
#define vpi vector<pii>
#define mp make_pair
#define fi first
#define se second
const int N = 18174, M = 27512, Q1 = 118, Q2 = 117;
const int QQ = Q1 * Q2 * 2;
int cnt;
long long collisions(std::vector<long long> x);
bool query(vl x){cnt += x.size();return collisions(x) != 0;
}
bool chkQ(){vl A;A.clear();for(int i = 1;i <= Q1;++i) A.pb(i * N);for(int i = 1;i <= Q2;++i) A.pb((Q1 * Q2 + i * Q1 + 1) * N);return query(A);
}
bool chk2(vl A,vl B){vl x;x.clear();for(int i = 0;i < A.size();++i) x.pb(A[i]);for(int i = 0;i < B.size();++i) x.pb(B[i]);return query(x);
}
int work(vl A,vl B){if(A.size() == 1 && B.size() == 1) return abs(A[0] - B[0]);if(A.size() < B.size()) swap(A,B);vl A1,A2;A1.clear();A2.clear();int nn = A.size() >> 1;for(int i = 0;i < A.size();++i){if(i < nn) A1.pb(A[i]);else A2.pb(A[i]);}if(chk2(A1,B)) return work(A1,B);return work(A2,B);
}
bool chk_vpi(vpi x){int a = 1;for(int i = 0;i < x.size();++i){for(int j = 1;j <= x[i].se;++j) a *= x[i].fi;}return query({1,a + 1});
}
int final_chk(int x){int y = x;vpi pi;pi.clear();for(int i = 2;i * i <= y;++i) if(y % i == 0){pi.pb(mp(i,0));while(y % i == 0){++pi[pi.size() - 1].se;y /= i;}}if(y > 1) pi.pb(mp(y,1));for(int i = 0;i < pi.size();++i){int l = 0,r = pi[i].se - 1,mid,ans = pi[i].se;while(l <= r){mid = (l + r) >> 1;pi[i].se = mid;if(chk_vpi(pi)){ans = mid;r = mid - 1;}else l = mid + 1;}pi[i].se = ans;}int a = 1;for(int i = 0;i < pi.size();++i){for(int j = 1;j <= pi[i].se;++j) a *= pi[i].fi;}return a;
}
int hack(){cnt = 0;if(chkQ()){for(int i = 1;i <= QQ;++i){if(query({1,i * N + 1})) return final_chk(i * N);}return -1; // unreachable}vl A,B;A.clear();B.clear();for(int i = 1;i <= N;++i) A.pb(i);for(int i = 1;i <= M;++i) B.pb(N * M + i * N + 1);return work(A,B);
}

相关文章：