我和我的兄弟共用一个 🚫 树 | 浅谈一类静态集合最大互质元素查询问题的高效解法

· · 算法·理论

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; } ``` ::::