问题概述

给定一个无限序列 ( S_0, S_1, \ldots )，其中每个 ( S_K ) 是一个有限正整数集合，满足以下条件：

1. 封闭性：对于任意 ( x, y \in S_K )，有 ( \gcd(x, y) \in S_K )。
2. 字典序：序列按“莱卡顺序”排列，定义如下：
   • 比较两个集合 ( A ) 和 ( B ) 时，先比较最大值 ( \max A ) 和 ( \max B )，若最大值相同，则递归比较 ( A \setminus {\max A} ) 和 ( B \setminus {\max B} ) 的顺序。
   • 规定 ( \max \emptyset = -\infty )。

给定 ( T ) 个查询，每个查询给出一个整数 ( K )，要求输出集合 ( S_K )。

算法分析

通过分析代码和题目要求，可以得出以下关键点：

1. 集合的性质：

   • 由于封闭性要求，集合中任意两个元素的最大公约数也必须在集合中。这意味着集合在取最大公约数运算下是封闭的。
   • 通过数学推导，这样的集合本质上是由其元素的最大值决定的。具体地，若集合中最大元素为 ( m )，则集合必须包含所有能通过不断取最大公约数从 ( m ) 及其它元素生成的数，且这些数不超过 ( m )。

2. 莱卡顺序的规律：

   • 莱卡顺序相当于按集合的二进制表示（bitmask）的数值大小排序，其中二进制位表示数字是否在集合中（第 ( i ) 位对应数字 ( i+1 )）。
   • 经过分析，合法的集合（满足封闭性）对应的二进制掩码在按数值排序后，恰好就是序列 ( S_0, S_1, \ldots )。因此，问题转化为：给定 ( K )，找到第 ( K ) 个合法的二进制掩码，并输出对应的集合。

3. 高效求解：

   • 直接生成所有合法掩码并排序是不可行的，因为 ( K ) 可以很大（最多 ( 10^9 )）。
   • 代码采用预计算和状态转移的方法：
     • 预计算一个表 to，用于处理低 21 位（即数字 1 到 21）的封闭性扩展。对于任意低 21 位的掩码，可以通过查表快速得到其封闭扩展结果。
     • 对于更大的数字（22 到 40），通过动态维护一个 40 位的掩码，并在添加新元素时，利用预计算的 z 表（存储 ( \gcd(i, j) )）来更新掩码，确保封闭性。
     • 通过一个巨大的预计算字符串 f，存储了每 ( B )（( B = 10^5 )）个掩码的起始状态。这样，对于给定的 ( K )，可以找到最近的起始状态，然后通过 nxt 函数逐步模拟到第 ( K ) 个状态。
     • nxt 函数实现了从当前掩码生成下一个合法掩码的过程，通过枚举高位并确保封闭性。

4. 时间复杂度：

   • 预计算时间复杂度为常数。
   • 对于每个查询，最多需要模拟 ( B ) 步（即 ( 10^5 ) 步），每步操作在 40 位掩码上进行，常数时间。
   • 总复杂度为 ( O(T \cdot B) )，在 ( T \leq 5 ) 时可接受。

算法标签

• 状态压缩：使用二进制掩码表示集合。
• 预计算：预处理低位的封闭性扩展表和每 ( 10^5 ) 步的起始状态。
• 模拟/递推：从起始状态逐步生成第 ( K ) 个状态。
• 数论：利用最大公约数的性质确保集合封闭性。

代码解释

• z[i][j]：预计算 ( \gcd(i+1, j+1) - 1 )，用于在掩码更新时找到新添加的数字对应的索引。
• to[s]：对于低 21 位的掩码 s，预计算其封闭扩展结果（即添加所有必需的公约数后的掩码）。
• nxt(s)：将掩码 s 增加到下一个合法掩码。首先将 s 加 1，然后从高位向低位检查，确保封闭性（即如果两个位都为 1，则它们的最大公约数对应的位也必须为 1），最后用 to 处理低 21 位。
• 巨大字符串 f：存储了每 ( 10^5 ) 个掩码的起始状态（经过 base64 编码）。通过查询 K 所在的块，加载起始掩码，然后模拟剩余步数。
• 输出时，统计掩码中 1 的个数并输出对应的数字。

总结

本题通过深入分析集合的性质和顺序定义，将问题转化为在合法状态空间中的顺序枚举问题。利用预计算和分块技巧，大大减少了每个查询的模拟步数，从而在时间和空间上均可行。算法结合了状态压缩、数论和预计算的技巧，是一道综合性较强的题目。