如何高效求解满足$f(a_i)-f(a_j)=f(a_k)$的数组完美三元组？

核心思路 #

原问题中的条件 f(a_i) - f(a_j) = f(a_k)（要求 1≤i<j<k≤n）可以等价变形为：

f(a_i) = f(a_j) + f(a_k)

这一转化是优化的关键，将三元组的约束聚焦到中间元素j的左右元素f值的和关系上。

关键观察 #

由于 a_i ≤ 1e6，其因数个数f(a_i)的取值范围非常有限——1e6以内的自然数最多有240个因数（例如720720）。我们记这个最大值为max_f，这个小范围的取值是将时间复杂度从O(n²)降到线性级别的核心依据。

具体实现步骤 #

1. 转换f值数组：将原数组a转换为对应的f值数组f_arr，其中f_arr[i] = f(a_i)（题目已说明f数组预处理完成，这一步可直接完成）。
2. 统计全局频次：创建数组total_count，其中total_count[v]表示整个f_arr中值为v的元素个数。
3. 维护左右侧频次并计算贡献：
   • 初始化两个数组：left_count（记录j左侧元素的f值频次）全为0；right_count初始化为total_count的拷贝。
   • 遍历每个索引j（从0到n-1）：
     • 首先将right_count[f_arr[j]]减1，此时right_count仅包含j右侧（k>j）元素的f值频次。
     • 若j满足1 ≤ j ≤ n-2（保证左侧存在i<j，右侧存在k>j），计算当前j的贡献：
       遍历所有可能的f值y（1到max_f），如果f_arr[j] + y ≤ max_f，则将left_count[f_arr[j] + y] * right_count[y]累加到总结果中。
     • 最后将left_count[f_arr[j]]加1，为下一个j的左侧频次统计做准备。
4. 累加所有j的贡献，最终得到完美三元组的总数。

复杂度分析 #

• 时间复杂度：O(n + max_f + n*max_f)。由于max_f≈240，n≤1e5，总操作数约为2.4e7，完全满足时间要求。
• 空间复杂度：O(max_f)，仅需存储三个频次数组，空间占用极小。

示例验证 #

假设原数组a = [6,2,3]，对应的f_arr = [4,2,2]：

• 处理j=1（中间元素，f值为2）：
  • left_count此时为{4:1}（仅包含左侧i=0的f值4）
  • right_count此时为{2:1}（仅包含右侧k=2的f值2）
  • 计算得f_j + y = 2+2=4，对应left_count[4] * right_count[2] =1*1=1，即唯一的完美三元组(i=0,j=1,k=2)，符合预期。

内容的提问来源于stack exchange，提问作者korangar leo