AcWing1310 数三角形

原题链接：AcWing1310

题目大意：给定一个 $n×m$ 的网格，请计算三点都在格点上的三角形共有多少个。

下图为 $4×4$ 的网格上的一个三角形。

注意：三角形的三点不能共线。

输入格式

输入一行，包含两个空格分隔的正整数 $m$ 和 $n$。

输出格式

输出一个正整数，为所求三角形数量。

数据范围

$1≤m,n≤1000$

输入样例

1

2 2

输出样例

1

76

组合计数，容斥原理

解法

首先n++, m++;转化为格点数，我们需要从 $n \times m$ 个格点中选出 $3$ 个合法格点构成三角形，那么显然我们只需要将 $C_{nm}^3$ 减去不合法的情况（即三点共线的情况）。

我们将三点共线的斜率分为三种情况分别统计：

1. 斜率不存在（即竖直）：$nC_m^3$
2. 斜率为 $0$（即水平）：$mC_n^3$
3. 斜率存在且不为 $0$，斜率为正，与斜率为负是对称的，那么只考虑前者即可。
   • 首先n--, m--; 还原为长度。
   • 我们在 $n \times m$ 的矩形中，枚举底为 $i$，高为 $j$ 的直角三角形，共有 $(n-i+1)(m-j+1)$ 种（当然，我们只考虑斜边斜率大于 $0$ 的情况）
   • 这样的直角三角形，其斜边上的两个端点一定在格点上，我们只需要考察斜边上除了端点，还存在的格点的数量，结论：有 $\mathrm{gcd}(i,j)-1$ 个。那么这个三角形的斜边对三点共线的贡献即为：$(\mathrm{gcd}(i,j)-1)$ 种。
   • 总结：共 $2(n-i+1)(m-j+1)(\mathrm{gcd}(i,j)-1)$ 种

最后，利用容斥原理，从总数减去不合法的即可。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL n, m;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

LL C(LL a, LL b) {
    return a * (a - 1) * (a - 2) / 6;
}

int main() {
    cin >> n >> m;
    n++, m++; // 转化为格点数
    LL res = C(n * m, 3) - n * C(m, 3) - m * C(n, 3);
    n--, m--; // 还原成长度
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            res -= 2 * (n - i + 1) * (m - j + 1) * (gcd(i, j) - 1);
    }
    cout << res << endl;
    return 0;
}