BZOJ 3505 [CQOI2014] 數三角形：組合數學與最大公約數巧解

補集思路

m×n 網格共有 (m+1)*(n+1) 個格點。任選三點構成三角形，總數 C(total, 3)。減去三點共線（退化）的情況即得答案。

共線三點計數

枚舉向量 (dx, dy)，其中 0≤dx≤m, 0≤dy≤n 且不全為 0。方向向量化為最簡形式 (dx/g, dy/g)，g = gcd(dx, dy)。該方向上任意兩點間隔 g 個格點，中間有 g-1 個點。以此向量為邊的三點共線組合數為 (g-1) * (m-dx+1) * (n-dy+1)。注意 dx>0 且 dy>0 時方向有正負兩種（斜率 ±），乘 2；軸平行方向乘 1。

代碼實現

long long ans = 1LL * (m+1)*(n+1);
ans = ans * (ans-1) * (ans-2) / 6;
for (int dx=0; dx<=m; ++dx)
    for (int dy=0; dy<=n; ++dy) if (dx||dy) {
        int g = gcd(dx, dy);
        ans -= 1LL * (g-1) * (m-dx+1) * (n-dy+1) * (dx && dy ? 2 : 1);
    }
cout << ans << endl;

注意使用 long long 防溢出。GCD 遞歸實現即可。