题解：P12541 [APIO2025] Hack!

· · 题解

题目大意：有一个数 n，你不知道是多少；你每次可以向交互库询问一个正整数集合 A（其中元素互不相同），交互库返回：将集合中的数对 n 取模后，有多少对数是相同的。也就是 \sum_{1 \le i < j \le |A|}[A_i \equiv A_j \pmod n]。你要通过若干次询问求出 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，如何从中具体找到哪两个数冲突？这里就要用到这类交互题常见的二分技巧：

总之，花费 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\}，满足 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，开销为 2p+3q；然后是对 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 集合的地位，这样开销就变成了 3p+2q，这样算出来的 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);
}