问题分析

我们需要选择两个数 $x$ 和 $y$（$1 \leq x, y \leq n$），使得 $x$ 和 $y$ 的因数个数的并集尽可能大。换句话说，我们要最大化 $d(x) \cup d(y)$ 的大小，其中 $d(k)$ 表示 $k$ 的所有正因数的集合。

核心算法

算法框架：深度优先搜索 + 质因数分解

使用深度优先搜索生成所有可能的 $(x, y)$ 对，但通过剪枝优化避免枚举所有情况。

关键观察

1. 数论性质：一个数的因数个数由其质因数分解决定
2. 搜索空间限制：只考虑前几个质数（到47为止）
3. 对称性剪枝：假设 $x \leq y$ 来避免重复
4. 边界剪枝：当 $x$ 或 $y$ 超过 $n$ 时停止

算法步骤详解

1. 质数预处理

const int prm[35] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};

使用前15个质数进行搜索。

2. 深度优先搜索

void dfs(int dep, ll x, ll y, ll dx, ll dy, ll dz, int las, int lasa, int lasb)

参数说明：

• dep：当前处理的质数索引
• x, y：当前两个数的值
• dx, dy：$x$ 和 $y$ 的因数个数
• dz：$x$ 和 $y$ 公因数的个数
• las, lasa, lasb：用于剪枝的指数限制

3. 剪枝策略

指数限制剪枝

// 对不同质数设置不同的指数上限
if (dep == 1 && max(a, b) - min(a, b) > 5) continue;
if (dep == 2 && max(a, b) - min(a, b) > 2) continue;
if (dep >= 3 && max(a, b) - min(a, b) > 1) continue;

对称性剪枝

if (x == y && a > b) continue;  // 避免重复

边界剪枝

if (min(x, y)*prm[dep] > n) {
    ans = max(ans, (Tup){dx + dy - dz, x, y});
    return;
}

4. 目标函数计算

目标是最小化：

$$f(x, y) = d(x) + d(y) - d(\gcd(x, y))$$

其中 $d(k)$ 是 $k$ 的因数个数。

算法标签

• 深度优先搜索 (DFS)
• 数论 (Number Theory)
• 质因数分解 (Prime Factorization)
• 剪枝优化 (Pruning)
• 组合优化 (Combinatorial Optimization)

复杂度分析

• 时间复杂度：$O(\text{状态数})$，通过剪枝大大减少
• 空间复杂度：$O(\text{递归深度})$

关键技巧

1. 因数个数计算

利用数论公式：如果 $n = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$，那么：

$$d(n) = (a_1+1)(a_2+1)\cdots(a_k+1)$$

2. 公因数个数计算

如果 $x = \prod p_i^{a_i}$，$y = \prod p_i^{b_i}$，那么：

$$d(\gcd(x,y)) = \prod (\min(a_i, b_i) + 1)$$

3. 渐进式剪枝

for (int j = 0; j <= 1; ++j)
    mn[0][j] = min({mn[0][j], (j ? mn[0][j-1] : 60), (b == j ? (int)a : 60)});

记录每个位置的最小指数要求，用于后续剪枝。

样例验证

对于样例 $n = 15$：

• 最优解：$x = 12$, $y = 10$
• $d(12) = \{1,2,3,4,6,12\}$（6个因数）
• $d(10) = \{1,2,5,10\}$（4个因数）
• 并集大小：$6 + 4 - 2 = 8$（去掉重复的1和2）

正确性证明

1. 完备性：通过DFS枚举所有可能的质因数组合，确保找到最优解。

2. 最优性：剪枝策略只排除不可能成为最优解的情况。

3. 高效性：通过多种剪枝策略将指数级问题转化为可处理规模。

该解法巧妙地利用了数论性质和搜索优化，在极大范围内（$n \leq 10^{16}$）高效解决了这个组合优化问题。