数形成三角形的三元组

Question

问题很简单；给定

n

(3 <= n <= 10^5)

，计算所有三元组

i, j, k

(0 < i < j < k <= n)

，以便它们可以是非简并三角形的边长。打印对

10^9

取模的答案。

我还没有找到最优解，只能暴力破解。

for (i = 1; i <= n-2; i++){
    for (j = i+1; j <= n-1; j++){
        for (k = j+1; k <= n; k++){
            if (i+j > k && i+k > j && j+k > i){
                res++;
            }
        }
    }
}

有什么想法吗？

Answer 1

任何边都不为零的三角形都是非退化的，因此

0 < i < j < k <= n

就是您需要知道的全部内容。

i+j > k && i+k > j && j+k > i

似乎是错误的。 该问题没有指出

i + j

必须大于

k

。边长为

1, 2, 3

的三角形不会退化。

要了解可能的解决方案，请考虑

n = 5

的可能结果：

1, 2, 3
1, 2, 4
1, 2, 5
1, 3, 4
1, 3, 5
1, 4, 5
2, 3, 4
2, 3, 5
2, 4, 5
3, 4, 5

这实际上只是

5 choose 3

，即从一组五个元素中挑选三个独特元素的方法数。

请参阅计算 n 选择 k 的最佳方法？了解如何计算答案。 要得到答案 mod 10⁹，只需在整个计算过程中进行模除即可。