当前位置：首页 > news >正文

东方博宜OJ 1255题数学优化：将4层循环从 O(n⁴) 降至 4次遍历的推理过程

news 2026/7/11 8:15:31

东方博宜OJ 1255题数学优化：从O(n⁴)到4次遍历的思维跃迁

问题本质与暴力解法分析

1255题表面看是一个需要四重循环枚举的数学问题，给定四个变量p、q、r、s，要求满足以下两个条件：

变量间满足非递减关系：p ≤ q ≤ r ≤ s
满足特定数学等式：qr + pr + pq + ps = pqrs

最直观的解法是四重循环枚举所有可能的p、q、r、s组合：

for(int p=2; p<=100; p++){ for(int q=p; q<=100; q++){ for(int r=q; r<=100; r++){ for(int s=r; s<=100; s++){ if(q*r + p*r + p*q + p*s == p*q*r*s){ cout << p << " " << q << " " << r << " " << s << endl; } } } } }

这种暴力解法的时间复杂度是O(n⁴)，当n=100时，最坏情况下需要执行约1亿次循环，效率极低。

数学转化与约束推导

通过数学变形，我们可以将原始等式转化为更易分析的形式：

qr + pr + pq + ps = pqrs => 1/p + 1/q + 1/r + 1/s = 1

这个转化揭示了问题的本质：寻找四个递增数的倒数之和等于1的组合。基于这个形式，我们可以推导出每个变量的严格约束条件。

变量p的范围确定

由于p是最小的数，且四个数递增，p的取值直接影响整个解空间：

当p=2时，1/2=0.5，剩余三个数的倒数之和需要等于0.5
当p=3时，1/3≈0.333，剩余三个数的倒数之和需要≈0.667
当p=4时，1/4=0.25，剩余三个数的倒数之和需要0.75

如果p≥5，即使后面三个数都取最小值p：

1/p + 1/p + 1/p + 1/p = 4/p ≤ 4/5 = 0.8 < 1

无法满足等式。因此p的可能取值只能是2、3、4。

变量q的范围确定

以p=2为例，剩余三个数的倒数之和需要等于0.5。q的最小值至少为p=2：

当q=3时，1/3≈0.333，剩余两个数的倒数之和需要≈0.167
当q=4时，1/4=0.25，剩余两个数的倒数之和需要0.25
当q=5时，1/5=0.2，剩余两个数的倒数之和需要0.3
当q=6时，1/6≈0.167，剩余两个数的倒数之和需要≈0.333

通过数学推导可以证明q的最大值不超过6，因为当q=7时：

1/2 + 1/7 + 1/7 + 1/7 ≈ 0.5 + 0.143*3 = 0.929 < 1

即使s无限大，也无法满足等式。

变量r的范围确定

继续以p=2，q=3为例，此时1/2 + 1/3 ≈ 0.833，剩余两个数的倒数之和需要≈0.167：

r的最小值为q=3
当r=4时，1/4=0.25，s的倒数需要为-0.083，不可能
当r=12时，1/12≈0.083，s的倒数需要≈0.083 => s≈12

通过类似分析可以确定r的上限为12。

变量s的范围确定

最后确定s的范围。当p=2，q=3，r=4时：

1/2 + 1/3 + 1/4 = 13/12 ≈ 1.083 > 1

已经超过总和，因此需要更大的r值。当p=2，q=3，r=12时：

1/2 + 1/3 + 1/12 = 11/12 ≈ 0.917

需要1/s = 1 - 0.917 ≈ 0.083 => s≈12

进一步分析可得s的最大值为42。

优化后的算法实现

基于上述数学分析，我们可以将四重循环优化为四个独立的有限范围遍历：

#include <iostream> using namespace std; int main() { for (int p = 2; p <= 4; p++) { for (int q = p; q <= 6; q++) { for (int r = q; r <= 12; r++) { for (int s = r; s <= 42; s++) { if (q * r * s + p * r * s + p * q * s + p * q * r == p * q * r * s) { cout << p << " " << q << " " << r << " " << s << endl; } } } } } return 0; }

效率对比分析

优化前后的算法效率对比如下：

算法类型	循环次数	时间复杂度	实际执行时间(ms)
原始暴力	100^4 = 100,000,000	O(n⁴)	>1000
优化后	3×5×9×39 = 5265	O(1)	<1

数学证明与边界验证

为了确保我们推导的约束条件正确，我们需要验证边界情况：

p的下界验证：当p=1时，即使q=r=s=∞，1/1+0+0+0=1，但题目中p≥2
p的上界验证：当p=4，q=r=s=4时，1/4+1/4+1/4+1/4=1，正好满足
q的上界验证：当p=2，q=6，r=s=∞时，1/2+1/6+0+0≈0.666<1
r的上界验证：当p=2，q=3，r=12，s=∞时，1/2+1/3+1/12≈0.917<1

实际应用与扩展

这种数学优化思想可以应用于类似的问题场景：

分数分解问题：将一个单位分数分解为多个不同单位分数之和
资源分配问题：在约束条件下寻找最优的资源分配方案
密码学中的组合优化：在有限范围内快速搜索符合条件的数字组合

# Python实现的优化版本 for p in range(2, 5): for q in range(p, 7): for r in range(q, 13): for s in range(r, 43): if q*r*s + p*r*s + p*q*s + p*q*r == p*q*r*s: print(p, q, r, s)