我和我的兄弟共用一个 🚫 树 | 浅谈一类静态集合最大互质元素查询问题的高效解法
EastSnowLotus
·
·
算法·理论
idea form HesHUI,hack 数据 from gpt6。
保证 AI 对本文的贡献不超过 50%,但并不保证贡献剩下部分的一定是人类。
记号
$\omega(x)$ 表示 $x$ 不同质因子的数量。
$(a,b)$ 表示 $\gcd(a,b)$。
$O$ 记号表示复杂度上界,$\Omega$ 记号表示复杂度下界。
# 问题引入
考虑如下问题:
给定一个静态集合 $S$ 和 $q$ 次询问,每次询问给定 $x$,求
$$
\max_{y\in S,\ (x,y)=1}y,
$$
不存在合法元素时返回 $0$,**强制在线**。
设集合中的数和询问值均为 $[1,V]$ 内的正整数。我们可以构造一个数据结构:预处理只依赖 $S$ 和 $V$,不需要提前知道询问,在预处理好值域内各数的质因子后,可以用 $O(1+\omega(x)^2)$ 的时间回答一次询问。
对于下文介绍的过滤下传实现,目前可以证明 $O(V^2)$ 的最坏预处理上界,并构造出 $\Omega(V^{3/2-o(1)})$ 的预处理下界。这里的下界针对最坏输入,并不是每个集合都需要这么久。
接下来把这个结构称为 **🚫 树**。
虽然看上去预处理很慢,但它的实际效率主要取决于出现了多少个状态,以及每个状态需要扫描多少个候选。这两个量在不少数据中都很小,因此实际表现会远好于复杂度上界。
下表使用几类固定集合,并为每类集合选取已测试的较慢询问模式。$R$ 表示相同 $\operatorname{rad}$ 的元素只保留最大值后,剩余的元素数量。
| $V$ | $\lvert S\rvert$ | $q$ | 压缩后 $R$ | 建树/ms | 查询核心/ms | 完整程序/s | 构造 |
| -----: | ---------------: | -----: | ---------: | -------: | ----------: | ---------: | ---------------- |
| $10^5$ | $10^3$ | $10^6$ | 1000 | 0.765 | 58.367 | 0.155 | 定向混合构造 |
| $10^5$ | $10^4$ | $10^6$ | 10000 | 11.358 | 64.017 | 0.242 | 定向混合构造 |
| $10^5$ | $10^5$ | $10^6$ | 60794 | 6.032 | 30.572 | 0.138 | 全集 |
| $10^6$ | 5 | $10^6$ | 5 | 0.322 | 86.665 | 0.233 | 35 次取模 |
| $10^6$ | 5 | $10^7$ | 5 | 0.148 | 857.032 | 1.787 | 35 次取模 |
| $10^6$ | $10^3$ | $10^6$ | 1000 | 5.996 | 73.750 | 0.250 | 定向混合构造 |
| $10^6$ | $10^4$ | $10^6$ | 10000 | 63.590 | 87.369 | 0.298 | 定向混合构造 |
| $10^6$ | $10^5$ | $10^6$ | 100000 | 611.614 | 77.891 | 0.830 | 定向混合构造 |
| $10^6$ | $10^5$ | $10^7$ | 100000 | 557.188 | 764.008 | 2.393 | 定向混合构造 |
| $10^6$ | 486993 | $10^6$ | 486993 | 2333.647 | 57.333 | 2.869 | 固定强数据 |
| $10^6$ | 486993 | $10^7$ | 486993 | 2517.485 | 628.946 | 4.460 | 固定强数据 |
| $10^6$ | $10^6$ | $10^6$ | 607926 | 65.268 | 30.878 | 0.324 | 全集 |
| $10^6$ | $10^6$ | $10^7$ | 607926 | 62.322 | 297.714 | 1.383 | 全集 |
| $10^9$ | $10^5$ | $10^7$ | 100000 | 416.881 | 1329.662 | 2.218 | 组合构造,稀疏版 |
| $10^9$ | $10^6$ | $10^6$ | 1000000 | 3845.940 | 121.647 | 4.672 | 组合构造,稀疏版 |
| $10^9$ | $10^6$ | $10^7$ | 1000000 | 4320.235 | 1245.012 | 5.900 | 组合构造,稀疏版 |
建树时间只计算结构构造;查询核心时间是不含读写的全部 $q$ 次询问总耗时;完整程序还包含读入、预处理和输出。时间取多次运行中位数,输出不经过终端渲染。构造性数据是已找到的慢例,不是对应参数的最坏时间上界。
## 表中数据
- **全集**:$S=[1,V]$,询问从若干小素数乘积的因数中随机抽取。
- **定向混合构造**:高处放质因子组合较复杂的数,低处优先放能在较多状态中存活的候选,并选择扫描量较大的方案;询问集中在取模次数较多的值上。
- **固定强数据**:将 $[1,800000]$ 与搜索得到的 2144 个高处候选取并集,再压缩为 486993 个代表。表中直接用这些代表作为 $S$,询问重复一个困难值。
- **35 次取模**:$S=\{930930,870870,690690,570570,510510\}$,重复询问 $x=392863$。原查询实现每次恰好做 35 次整除测试。
- **组合构造**:从 $2$ 到 $31$ 的 11 个素数中任选 6 个,得到 $\binom{11}{6}=462$ 种质因子集合。每种取一个数,只乘已有质因子的幂将它增大,其余元素取大于 31 的前 $\lvert S\rvert-462$ 个素数。询问从这 462 个六元子集的乘积中随机抽取。
**稀疏版**描述的是实现方式:用哈希表记录实际出现的状态,不开长度为 $V$ 的状态数组;只筛出不超过 $\sqrt V$ 的素数,遇到节点最大值时才分解并缓存。儿子仍由过滤父候选数组得到。组合数据的 $\operatorname{rad}$ 本来就两两不同,因此 $R=|S|$。
表中查询采用“枚举当前最大值的质因子”的写法,不需要分解询问值;后文会给出它与另一种查询写法的复杂度。
# 基本思路
设 $y$ 是当前候选中的最大值。当 $(x,y)=1$ 时,答案就是 $y$。
否则,取一个同时整除 $x$ 和 $y$ 的质数 $p$。所有含质因子 $p$ 的候选都不可能成为答案,可以全部删除,再考察剩余候选的最大值。
整个过程就是不断禁止共同质因子,直到找到合法的最大值。由于 $S$ 不变,可以提前建立所有可能的禁止状态。
# 🚫 树的状态
设已经禁止的不同质数的乘积为 $f$,定义当前候选集合
$$
A_f=\{y\in S:(y,f)=1\}.
$$
例如 $f=14$,就表示候选不能含有质因子 $2$ 或 $7$。
根节点对应 $f=1$,此时没有任何限制,候选就是整个集合。
对于一个非空状态,我们只需要永久记录:
- 当前最大值 $y_f=\max A_f$;
- $y_f$ 的不同质因子;
- 再禁止其中每个质因子之后,应该走到哪个状态。
如果 $p\mid y_f$,再禁止 $p$ 后的新状态就是 $fp$。因为 $(y_f,f)=1$,所以 $p\nmid f$,每次下行都会加入一个此前没有禁止过的质数。
同一个 $f$ 对应的候选集合完全确定,和到达它的顺序无关。因此需要记忆化:相同状态只建立一次。
虽然称为树,但合并相同状态后,实际是一张有向无环图。
# 建树流程
## 候选压缩
如果
$$
\operatorname{rad}(a)=\operatorname{rad}(b),\qquad a<b,
$$
那么对于任意询问,$a$ 和 $b$ 要么同时合法,要么同时不合法。既然 $b$ 更大,$a$ 就不可能成为答案。
因此,对于相同的 $\operatorname{rad}$,只保留最大的元素。将剩下的 $R$ 个元素按数值从大到小排列,得到根候选数组。
## 过滤下传
假设当前正在建立状态 $f$,候选数组为 $A$,且已经按降序排列。
1. 如果 $f$ 已经建立过,直接返回记忆结果。
2. 如果 $A$ 为空,记下这个空状态。
3. 否则取 $y=A_0$,作为当前最大值。
4. 枚举 $y$ 的每个不同质因子 $p$。
5. 若 $fp\le V$ 且该状态尚未建立,扫描整个 $A$,保留所有不被 $p$ 整除的元素,作为儿子的候选数组,继续递归。
因为只删除元素,过滤后的数组依然有序,不需要重新排序。
已经建立过的状态应当直接连接,**不要先过滤数组,再检查记忆化**。空状态也要记忆,否则可能被反复建立。
## 状态剪枝
沿着某次询问的路径,所有已经禁止的质数都整除 $x$,新加入的 $p$ 也整除 $x$,所以
$$
fp\mid x.
$$
如果 $fp>V$,就意味着 $x>V$,这不可能。因此这样的儿子不会被任何合法询问经过,可以直接不建。
该剪枝使用的是询问值的上界。
# 询问流程
从根节点开始,设当前最大值为 $y$。
- 如果当前状态为空,返回 $0$。
- 如果 $(x,y)=1$,返回 $y$。
- 否则找一个共同质因子 $p$,走到状态 $fp$。
这样做不会删掉正确答案:因为 $p\mid x$,被删掉的所有数原本就不合法。
而当当前最大值与 $x$ 互素时,它已经是所有剩余候选中最大的数,因此就是答案。
例如
$$
S=\{30,21,10,7,1\},\qquad x=6.
$$
询问过程如下:
| 当前 $f$ | 当前候选 | 最大值 | 操作 |
| -------: | ------------ | -----: | -------------------------- |
| 1 | 30,21,10,7,1 | 30 | 共同质因子为 2,走到 $f=2$ |
| 2 | 21,7,1 | 21 | 共同质因子为 3,走到 $f=6$ |
| 6 | 7,1 | 7 | 与 6 互素,返回 7 |
预处理不依赖将来的询问,当前询问依赖上一次答案时也可以直接处理。
# 算法效率
## 询问复杂度
设 $s=\omega(x)$。
每次下行都加入一个新的、整除 $x$ 的质数,因此至多下行 $s$ 次,至多访问 $s+1$ 个非空节点。
如果已经获得 $x$ 的不同质因子,可以在每个节点枚举这些质因子,检查是否整除当前最大值。找到共同质因子 $p$ 后,令 $f\gets fp$,直接通过状态编号定位新节点。
由于建树时已经枚举了当前最大值的全部质因子,这个后继一定已经准备好。使用按 $f$ 索引的数组时,定位新节点为 $O(1)$。
每个节点至多检查 $s$ 个质数,总计至多 $s(s+1)$ 次整除测试,因此单次询问为
$$
\boxed{O(1+\omega(x)^2)}.
$$
加上 $1$ 是为了覆盖 $x=1$。若没有预先获得 $x$ 的质因子,还需要另计分解 $x$ 的时间。
另一种写法是直接枚举当前最大值 $y$ 的质因子,表中的测试程序就采用这种方式。令
$$
K(V)=\max_{1\le a\le V}\omega(a),
$$
则它的单次询问上界为
$$
\boxed{O\bigl(K(V)(\omega(x)+1)\bigr)}.
$$
这种写法不需要对询问值进行质因数分解,因此在大值域的稀疏实现中也很方便。
| $V$ | $K(V)$ | 最多访问的非空节点 |
| -----: | -----: | -----------------: |
| $10^5$ | 6 | 7 |
| $10^6$ | 7 | 8 |
| $10^9$ | 9 | 10 |
例如前 7 个素数之积为 $510510$,前 8 个素数之积已超过 $10^6$,所以 $10^6$ 内至多有 7 个不同质因子。
因此,无论采用哪种写法,这几档值域下的询问都很短。
## 建树复杂度
设实际建立了 $H$ 个非空节点和 $E$ 个空状态,总状态数为
$$
T=H+E.
$$
建树最主要的工作是过滤候选。设累计检查了 $W$ 个候选元素,则在已经得到质因子表和根候选数组的情况下,建树时间为
$$
O(V+K(V)H+W).
$$
其中 $O(V)$ 用于初始化记忆数组,$O(K(V)H)$ 用于枚举节点的分支。
每个首次建立的非根状态,都需要扫描它第一次到达时的父候选数组,因此
$$
W=
\sum_{\text{首次建立的非根状态 }g}
|A_{\operatorname{par}(g)}|.
$$
这个量不能直接看成节点数。即使只有几千个节点,如果每次都扫描几十万个候选,累计工作量也会很大。
每个父候选数组至多长 $R$,因此
$$
W\le R(T-1).
$$
每个状态编号 $f$ 都是一个不超过 $V$ 的无平方因子数,而且相同状态只会建立一次,所以
$$
T\le V.
$$
于是 $R\le V$、$T\le V$,得到
$$
W=O(V^2).
$$
加上 $O(V\log\log V)$ 的质因子预处理,以及集合收集和压缩,得到原过滤实现的安全预处理上界
$$
\boxed{O(V^2)}.
$$
这只是一个宽松上界,目前没有证明它是紧界。
## 实测表现
状态合并和乘积剪枝会显著减少实际节点数。对于 $[1,10^6]$ 的全集,压缩后仍有 $607926$ 个候选,但只建立了 $61$ 个非空节点,累计检查约 $2393$ 万个候选;固定强数据有 $2609$ 个非空节点,累计检查约 $7.37$ 亿次。
组合构造的复杂质因子只来自 11 个小素数,实际建立了 $1282$ 个非空节点。值域增大,并不意味着需要遍历整个值域。
下面补充均匀随机数据:从 $[1,V]$ 无放回抽取 $\lvert S\rvert$ 个数作为集合,每次询问独立均匀抽取 $x$。每档使用 3 个随机种子,各重复 3 次;时间取 9 次结果的中位数,节点数给出三个种子间的范围。
| $V$ | $\lvert S\rvert$ | $q$ | 非空节点数范围 | 建树/ms | 查询核心/ms | 完整程序/s |
| -------: | ---------------: | -----: | -------------: | ------: | ----------: | ---------: |
| $10^{5}$ | $10^4$ | $10^6$ | 2–35 | 0.498 | 15.056 | 0.064 |
| $10^{6}$ | $10^5$ | $10^6$ | 5–261 | 4.997 | 13.066 | 0.110 |
| $10^{6}$ | $5\times10^5$ | $10^6$ | 30–54 | 30.476 | 12.870 | 0.160 |
| $10^{9}$ | $10^5$ | $10^6$ | 12–282 | 9.323 | 3.287 | 0.068 |
| $10^{9}$ | $10^6$ | $10^6$ | 31–384 | 318.814 | 12.353 | 0.482 |
| $10^{9}$ | $10^6$ | $10^7$ | 31–384 | 327.148 | 125.751 | 1.045 |
这批随机测试与前表环境不同,不直接比较耗时倍数。同一环境下,$V=10^9,\lvert S\rvert=10^6$ 的组合构造建树约为 $2637$ ms,可作为参照。
这些随机样本的非空节点数均未超过 384。实际效率主要由状态数和累计候选扫描量决定,随机集合在本次测试中产生的状态明显少于定向构造数据。
## 空间复杂度
节点永久保存的只有最大值、质因子和后继。候选数组只是在递归建树时临时存在,返回后即可释放。
递归深度至多为 $K(V)$,每层数组容量至多为 $R$,所以临时候选空间为
$$
O(K(V)R),
$$
而不是累计扫描量 $W$。
加上质因子表、记忆数组和节点,稠密版本的空间为
$$
O\bigl(VK(V)+HK(V)+RK(V)+|S|\bigr).
$$
# 简单的 hack 构造思路
想让这个实现变慢,需要同时满足两件事:
1. 高处的候选能制造许多不同的禁止状态。
2. 大量低处候选在这些状态中始终存活,从而被反复扫描。
一个容易理解的构造是:取 $t^2$ 个不同质数,最大者为 $P$,将它们分成 $t$ 组,每组 $t$ 个,令
$$
V=P^t.
$$
每组先将自己的质数全部相乘,再只乘已有质因子的幂,将这个数抬到大于 $V/P$、但不超过 $V$。这样得到 $t$ 个高处候选,而且它们的质因子集合两两不相交。
再加入 $b$ 个位于 $(P,V/P]$ 中的素数作为低处候选。
禁止某个高处候选的一个质因子时,只会删除这一组的高处候选,其他组和全部低处素数都不受影响。
因此,每组都有 $t$ 种不同的禁止选择,处理完全部 $t$ 组后,至少出现
$$
t^t
$$
个不同状态。它们的禁止乘积都不超过 $P^t=V$,不能被值域剪枝删掉,也不能被记忆化合并。
每次建立新状态时,那 $b$ 个低处候选仍然在数组里,所以
$$
W\ge b\,t^t.
$$
如果使用前 $t^2$ 个素数,标准素数估计给出
$$
P=\Theta(t^2\log t),\qquad
b=V^{1-o(1)},\qquad
t^t=V^{1/2-o(1)}.
$$
因此,对这一族构造,
$$
\boxed{W=\Omega(V^{3/2-o(1)})}.
$$
这说明过滤下传实现确实可以被构造到明显超线性。它的实用价值来自很多数据中很小的实际状态数,而不是已经有了近线性的最坏情况保证。
# 例题应用
[CF1285F — Classical?](https://codeforces.com/problemset/problem/1285/F) 要求不同位置的两数的最大 LCM,$a_i\le 10^5$。设 $D$ 为原集合中所有数的因数组成的集合。对原来的任意两数 $a,b$,可以把 $\operatorname{lcm}(a,b)$ 中每个质数的最高次幂分给包含它的一侧,得到互素的 $u\mid a,v\mid b$,满足 $uv=\operatorname{lcm}(a,b)$。
反过来,对互素的 $u,v\in D$,若它们分别来自不同位置,则 $uv$ 不超过这两个原数的 LCM;若只能来自同一位置,则 $uv$ 不超过原集合最大值 $M$。由于原数组至少有两个位置,最大 LCM 至少为 $M$,因此答案恰为
$$
\max\left(M,\max_{u,v\in D,\ (u,v)=1}uv\right).
$$
代码先按质数下传标记求因数闭包,再按 $\operatorname{rad}$ 压缩建树。这里添加因数是最大 LCM 问题的等价转化;原来的静态集合互素最大值问题仍只保留原集合中的候选。
[线上提交 398038217](https://codeforces.com/contest/1285/submission/398038217) 使用 C++23(GCC 14-64),结果为 **Accepted,62 ms,2100 KB**,通过全部 171 个测试。这里记录的是完整程序的评测耗时。
# C++ 实现
下面沿用之前测速的数组版,固定 $V=10^6$,使用过滤下传和枚举节点最大值质因子的询问方式,去掉测速统计部分。代码支持 C++14。
输入依次为 $n,q$、$n$ 个集合元素和 $q$ 个询问值,所有数均在 $[1,V]$ 内;无解返回 $0$。
::::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
const int V=1000000;
struct Sieve{
int m;
vector<int> spf,rad,prime;
vector<array<int,7>> fac;
vector<unsigned char> cnt;
Sieve(int M):m(M),spf(M+1),rad(M+1),fac(M+1),cnt(M+1){
rad[1]=1;
for(int i=2;i<=m;i++){
if(!spf[i]) prime.push_back(i),spf[i]=i;
for(int p:prime){
if(1LL*i*p>m) break;
spf[i*p]=p;
if(p==spf[i]) break;
}
int x=i;
rad[i]=1;
while(x>1){
int p=spf[x];
fac[i][cnt[i]++]=p;
rad[i]*=p;
do{x/=p;}while(x%p==0);
}
}
}
};
struct Node{
int mx,son[7];
};
struct Tree{
const Sieve &a;
vector<int> id;
vector<Node> tr;
int rt=0;
Tree(const Sieve &A):a(A),id(a.m+1,-1),tr(1){}
int build(const vector<int> &S,int f){
if(id[f]!=-1) return id[f];
if(S.empty()) return id[f]=0;
int u=tr.size();
id[f]=u;
tr.push_back({});
int y=S[0];
tr[u].mx=y;
for(int i=0;i<a.cnt[y];i++){
int p=a.fac[y][i];
if(f>a.m/p) continue;
int g=f*p;
if(id[g]!=-1){
tr[u].son[i]=id[g];
continue;
}
vector<int> T;
T.reserve(S.size());
for(int x:S){
if(x%p) T.push_back(x);
}
int v=build(T,g);
tr[u].son[i]=v;
}
return u;
}
int query(int x)const{
int u=rt;
while(u){
int y=tr[u].mx,i=0;
while(i<a.cnt[y]&&x%a.fac[y][i]) i++;
if(i==a.cnt[y]) return y;
u=tr[u].son[i];
}
return 0;
}
};
vector<int> unique_rad(const vector<int> &S,const Sieve &a){
vector<unsigned char> has(a.m+1),used(a.m+1);
for(int x:S) has[x]=1;
vector<int> res;
for(int x=a.m;x>=1;x--){
if(has[x]&&!used[a.rad[x]]){
used[a.rad[x]]=1;
res.push_back(x);
}
}
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n,q;
if(!(cin>>n>>q)) return 0;
vector<int> S(n);
for(int &x:S) cin>>x;
Sieve a(V);
auto R=unique_rad(S,a);
Tree t(a);
t.rt=t.build(R,1);
for(int i=0,x;i<q;i++){
cin>>x;
cout<<t.query(x)<<'\n';
}
return 0;
}
```
::::