正整數解計數：x + y + z = n 的組合數學與 OJ 解法

問題重述

給定正整數 n (n ≥ 3)，求正整數解 (x, y, z) 滿足 x + y + z = n 的個數。x, y, z ≥ 1。

組合數學解法（推薦）

經典星條法：

• 將 n 視為 n 顆星星 ★。
• 在 n-1 個間隙中選 2 個位置放隔板 |，分成三段，每段至少 1 顆星。
• 方案數 = C(n-1, 2) = (n-1)(n-2)/2。

驗證樣本：

• n=3：C(2,2)=1 → (1,1,1)
• n=4：C(3,2)=3 → (1,1,2) 排列 3 種
• n=5：C(4,2)=6

完整解法（O(1) 公式）

#include <stdio.h>

int main(void)
{
    long long n;
    while (scanf("%lld", &n) == 1) {
        if (n < 3) continue;               // 題目保證 n ≥ 3
        long long ans = (n - 1) * (n - 2) / 2;
        printf("%lld\n", ans);
    }
    return 0;
}

替代方案：三重迴圈暴力（僅適合極小 n）

int count = 0;
for (int x = 1; x < n; x++)
    for (int y = 1; y < n - x; y++) {
        int z = n - x - y;
        if (z >= 1) count++;
    }

時間複雜度 O(n²)，n 較大時會超時。本題無明確上限，必須使用公式法。

關鍵點

• 正整數解：x, y, z ≥ 1，非負整數解公式為 C(n+2, 2)，切勿混淆。
• 輸入多組、至 EOF：while (scanf(...) == 1)。
• 整數運算：(n-1)*(n-2) 必為偶數，整除無餘數；用 long long 防溢位。
• 邊界：n=3 時 (2*1)/2 = 1 正確。

延伸：k 個變數的正整數解

x₁ + x₂ + ... + xₖ = n, xᵢ ≥ 1 → C(n-1, k-1)。

本題 k=3，故 C(n-1, 2)。