算法題精解：N×N×N 正方體中公共點不超過 2 的小正方體對數公式推導

題目重述

邊長為 N 的大正方體，切分為 N³ 個單位小正方體。求：**任意兩個小正方體公共頂點數 ≤ 2 的無序對數**。即兩小塊**不共用整個面**（公共面=4個公共頂點）。

分類計數法核心思想

按小正方體在大正方體中的位置分類，計算每類小塊的「鄰面數」（與之共用面的小塊數），用**總數減去鄰面數再減去自身**得到符合條件的配對數，最後除以 2 去重。

四類位置與鄰面數

推導過程

對某類塊，符合條件的配對數 = 總塊數 N³ - 自身 1 - 鄰面塊數。
所有塊配對總和 = Σ [數量ᵢ × (N³ - 1 - 鄰面數ᵢ)]。
每對被算兩次（A 算 B，B 算 A），最終結果除以 2。

通用公式 (N > 1)

Pairs(N) = ½ × [ 8(N³-4) + 12(N-2)(N³-5) + 6(N-2)²(N³-6) + (N-2)³(N³-7) ]

驗證樣例

代碼實現 (O(1))

long long countPairs(int N) {
    if (N <= 1) return 0;
    long long n = N;
    long long n3 = n * n * n;
    long long n2 = n - 2;
    long long term1 = 8 * (n3 - 4);
    long long term2 = 12 * n2 * (n3 - 5);
    long long term3 = 6 * n2 * n2 * (n3 - 6);
    long long term4 = n2 * n2 * n2 * (n3 - 7);
    return (term1 + term2 + term3 + term4) / 2;
}

思維拓展

• **幾何組合學**：將空間問題轉化為分類計數 + 容斥原理。
• **對稱性利用**：立方體高度對稱，僅需分析 1/48 區域再乘以對稱係數。
• **推廣**：長方體、高維超立方體、不同「公共頂點數」閾值。

此題考察**空間想像、分類討論、代數歸納**綜合能力，屬經典面試/競賽好題。