1310 数三角形

组合数 线段中整点个数 容斥原理 T3 todo #2240. 「CQOI2014」数三角形 - 题目 - LibreOJ (loj.ac)

题目描述

给定一个 $n\times m$ 的网格，请计算三点都在格点上的三角形共有多少个。下图为 $4\times 4$ 的网格上的一个三角形。

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

输入格式

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

输出格式

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

样例

输入

2 2

输出

76

数据范围与提示

对于所有数据，$1\le m,n\le 1000$。

思路

给一个 $n\times m$ 的网格, 像这样三点都在点上的三角形有几个？ 样例是 $2\times 2$ 的网格： 依然是先选定一个点之后再看其他的点, $2\times 2$ 的网格中一共有 $3\times 3=9$ 个点, 而我们选其中 $3$ 个点, 共有 $C_9^3=\frac{9\times 8\times 7}{2\times 3}=84$。 但显然答案是 $76$ 个, 也就是说我们需要找到无解情况并将其减去。像这样的情况就是无解情况, 那么再减去行的 $3$ 个, 和列的 $3$ 个, 结果就是 $78$ 个。依然很多, 说明这种情况没算上： 算上之后再减去 $2$ 就是正确答案 $76$。

若直接整体做, 第一个点有 $9$ 种选法, 第二个点只需要与第一个点不同就行, 有 $8$ 种选法, 但第三个点就不好确定, 前两种情况的选法不同, 第三种也不同。

用另外一种思想, 即容斥原理, 或称补集思想, 先求出总的方案数, 然后减去无解的方案数即可。

给一个含有 $n\times m$ 个点的矩形, 总选择方案数为 $C_{n\times m}^3$, 而不合法的方案是三个点在一个直线上时, 可以启发地思考, 在矩形左下角建立坐标系, 无解情况的斜率有一下几种：

• $k=0$, 在一行中选 $3$ 个点, 共有 $n$ 行： $n\times C_m^3$
• $k=+\infty$, 在一列中选 $3$ 个点, 共有 $m$ 列： $m\times C_n^3$
• $k>0$, 找一种枚举方案, 先找最左下的点, 此时根据第一个点确定的情况, 会把所有方案分成 $n\times m$ 类, 再分别求每一类的情况, 那么另外两点一定在 $a$ 点上方： 接着再去枚举右上角的点, 有 $(n-i)\times (m-j)$ 种选择。 此时 $a,c$ 点已经确定, $b$ 点只能在由 $a,c$ 两点确定的线段上选一个点, 故我们需要求 $a,c$ 两点间有多少个整点, 即线段整数点数问题。 则整数点数量为：$gcd(i,j)$ , 若不包含 $a$ 端点则再减一。 证明： 对于整数点 $d_1,d_2$ 因为是在 线段$ab$ 上, 故 线段$ad$ 的斜率和 线段$ab$ 的斜率相等, 则在求 $d$ 点时, 需要在满足 $\frac{y_d}{x_d}=\frac{y_2-y_1}{x_2-x_1}$ 的情况下划分, 也就是说, 若划分了 $n$ 分, 每份的相对与点$a$的坐标是 $(\frac{x_2-x_1}{n},\frac{y_2-y_1}{n})$, 且需要满足划分后的点为整数, 还要使划分的份数 $n$ 最多, 故只有 $n=gcd(x_2-x_1,y_2-y_1)$ 满足要求。

那么最终结果就是 $\sum _{1\le i\le n,1\le j\le m}[gcd(i,j)-1](n-1)(m-1)$ 。 而对与 $k<0$, 因为从矩形中线轴对称后, 所有 $k>0$ 的直线都对应一个 $k<0$ 的直线, 故 $k>0$ 和 $k<0$ 的方案数相同, 直接加两倍就行了。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 1e3 + 10;
typedef long long LL;
 
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
 
LL C(int n)
{
    return (LL)n * (n - 1) * (n - 2) / 6;
}
 
int main()
{
    int n, m;
    cin >> n >> m;
    n++, m++;
    LL res = C(n * m) - (LL)n * C(m) - (LL)m * C(n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            res -= 2LL * (gcd(i, j) - 1) * (n - i) * (m - j);
    cout << res << endl;
 
    return 0;
}