ZOJ 3647 Gao the Grid：網格三角形計數（暴力枚舉優化）

ZOJ 3647 Gao the Grid：網格三角形計數（暴力枚舉優化）

題目大意

n×m 網格點（(n+1)×(m+1) 個點）。選 3 點組成三角形（非共線）。求三角形總數。n,m ≤ 1000，多測試案例。

數學推導

1. 總點數 P = (n+1)*(m+1)，任選 3 點：C(P, 3)
2. 扣除共線三點：
   　　水平：(n+1) * C(m+1, 3)
   　　垂直：(m+1) * C(n+1, 3)
3. 扣除斜線共線：枚舉向量 (dx, dy)，dx≥1, dy≥1，gcd(dx,dy)=g>1 表示中間有 g-1 個網格點共線。
   　　每對 (dx,dy) 貢獻：2 * (g-1) * (n+1-dx) * (m+1-dy)（2 為正負斜率）

AC 代碼

#include 
#include 
using namespace std;
typedef long long ll;

ll C3(ll x) { return x*(x-1)*(x-2)/6; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

int main() {
    ll n, m;
    while (~scanf("%lld%lld", &n, &m)) {
        ++n; ++m; // 點數
        ll ans = C3(n*m) - C3(n)*m - C3(m)*n;
        for (ll dx = 2; dx < n; ++dx)
            for (ll dy = 2; dy < m; ++dy) {
                ll g = gcd(dx, dy) - 1;
                if (g > 0)
                    ans -= g * (n-dx) * (m-dy) * 2;
            }
        printf("%lld\n", ans);
    }
    return 0;
}

關鍵點

• 雙重循環枚舉 dx,dy 實為「暴力」但 n,m≤1000 時 O(nm) ≈ 10⁶ 完全可行
• gcd(dx,dy)-1 為向量內部網格點數
• 乘 2 處理正負斜率對稱
• 樣例：2×2 網格 → 9點，C(9,3)=84，扣水平垂直 8 個 → 76

複雜度

• 時間：O(n m log max(n,m)) 主要在 gcd
• 空間：O(1)

此題展示了組合數學 + 數論（gcd）解決幾何計數問題，看似暴力實則最優。