NYOJ 982 三角形計數：數學推導與 O(1) 查詢解法

問題描述

給定長度為 1, 2, …, n 的 n 根桿，任選 3 根組成三角形。兩三角形至少有一邊長不同即視為不同。求不同三角形個數。多測試用例，n ≤ 1,000,000，以 n < 1 結束。

數學推導

1. 固定最長邊 x

設另兩邊為 y, z（y ≤ z < x），三角不等式要求 y + z > x ⇒ z > x - y。故 z 範圍：x - y < z < x。

2. 計算固定 x 時的合法 (y, z) 對數

• y 從 1 到 x-1 遍歷。
• y=1 時：x-1 < z < x 無整數解。
• y=2 時：z = x-1（1 解）。
• y=3 時：z = x-1, x-2（2 解）。
• …
• y=x-1 時：z = x-1, x-2, …, 2（x-2 解）。
• 總解數（含重複與 y=z）：0+1+2+…+(x-2) = (x-1)(x-2)/2。

3. 去重

• 每個三角形被計算了兩次（y,z 交換對稱）。
• 等腰三角形 (y=z) 被重複計算：y 從 ⌊x/2⌋+1 到 x-1，共 ⌊(x-1)/2⌋ 個。
• 去重後：C(x) = [ (x-1)(x-2)/2 - ⌊(x-1)/2⌋ ] / 2。

4. 前綴和遞推

答案 F(n) = Σ_{x=1..n} C(x)，遞推式：F(n) = F(n-1) + C(n)，F(1)=F(2)=F(3)=0。

代碼實現（預計算 + O(1) 查詢）

#include <stdio.h>

long long ans[1000005];

int main()
{
    ans[1] = ans[2] = ans[3] = 0;
    for (long long x = 4; x <= 1000000; ++x)
        ans[x] = ans[x-1] + ((x-1)*(x-2)/2 - (x-1)/2) / 2;

    int n;
    while (~scanf("%d", &n)) {
        if (n < 1) break;
        printf("%lld\n", ans[n]);
    }
    return 0;
}

複雜度分析

• 預計算：O(N) = 10⁶ 次簡單運算，極快。
• 查詢：O(1) 直接輸出 ans[n]。
• 空間：long long[1000005] ≈ 8 MB，符合限制。

關鍵細節

1. 使用 long long 防止中間結果溢出（n=10⁶ 時答案約 4×10¹⁶）。
2. (x-1)/2 整數除法自動向下取整，等價於 ⌊(x-1)/2⌋，無需分奇偶討論。
3. ~scanf 技巧：scanf 返回讀取項數，EOF 為 -1，按位取反為 0 假，結束循環。

測試樣例

輸入：
5
8
0

輸出：
3
22