统计边长小于N的不等边三角形总数求O(n)高效C++实现算法

架构老林

2026-10-4

不等边三角形计数O(1)优化方案

问题明确

我们需要统计满足 a < b < c < N 且 a + b > c 的正整数三元组总数量，也就是所有边长严格小于N的不等边三角形个数，默认按边长升序排列避免重复计数。

优化思路

原O(n²)算法在N=1e5时运算量达到1e10级别，会严重超时。我们可以通过数学推导直接得到闭式解，时间复杂度降到O(1)，远优于要求的O(n)。
对固定最长边c的符合条件的二元组(a,b)求和后，最终得到无误差的整数计算公式：

当 N 为偶数时：总数量 = N * (N - 2) * (2 * N - 5) / 24
当 N 为奇数时：总数量 = (N - 1) * (N - 3) * (2 * N - 1) / 24
注：N最大为1e5时计算结果约为4e13，远超32位int的存储上限，必须用64位长整型存储结果

优化后代码

typedef long long ll;
ll solve(int n) {
    if (n < 4) return 0; // 边长均小于4时不存在符合要求的不等边三角形
    ll res;
    if (n % 2 == 0) {
        res = (ll)n * (n - 2) * (2 * n - 5) / 24;
    } else {
        res = (ll)(n - 1) * (n - 3) * (2 * n - 1) / 24;
    }
    return res;
}