OJ題解：正整數解個數 - x+y+z=n 組合數學

題目轉化

求正整數解 (x,y,z) 滿足 x+y+z=n (n≥3) 的個數。
令 x'=x-1, y'=y-1, z'=z-1，則 x',y',z' ≥ 0 且 x'+y'+z' = n-3。
這是經典「將 n-3 個相同球放入 3 個盒子」問題，解數為組合數：

C((n-3)+3-1, 3-1) = C(n-1, 2) = (n-1)(n-2)/2

驗證樣本

n=3: (2*1)/2 = 1  → (1,1,1)           ✓
n=4: (3*2)/2 = 3  → (1,1,2)及排列     ✓
n=5: (4*3)/2 = 6  → (1,1,3)(1,2,2)及排列 ✓

O(1) 閉合公式實作

#include <stdio.h>

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n >= 3) {
        long long ans = 1LL * (n - 1) * (n - 2) / 2;
        printf("%lld\n", ans);
    }
    return 0;
}

原代碼三層迴圈分析

for (a=1; a<n; a++)
  for (b=1; b<n-a; b++) {
    c = n - a - b;
    if (c >= 0) m++;
  }

• 時間複雜度 O(n²)，n 較大時極慢
• 邏輯正確但非最優
• 條件 c >= 0 恆成立 (因 b < n-a)，可省略

數學推導補充

非負整數解 x₁+...+xₖ = N 個數為 C(N+k-1, k-1) (隔板法/Stars and Bars)。
本題 k=3, N=n-3 → C(n-1, 2)。