题解：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

，如何从中具体找到哪两个数冲突？这里就要用到这类交互题常见的二分技巧：

将集合 $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\}

，满足

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

。

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

CPP

#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);
}

题解：P12541 [APIO2025] Hack!

文章操作

相关推荐

评论

题解：P12541 [APIO2025] Hack!