1310. 数三角形（组合数学）

1310. 数三角形（组合数学） 题目描述

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

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

输入格式

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

输出格式

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

数据范围

1≤m,n≤1000

输入样例
2 2
输出样例
76

题目分析

我 们 直 接 算 组 成 三 角 形 的 数 量 并 不 好 算 ， 因 此 我 们 可 以 反 过 来 ， 先 算 出 所 有 的 选 择 ， 再 减 去 其 中 不 合 法 的 方 案 我们直接算组成三角形的数量并不好算，因此我们可以反过来，先算出所有的选择，再减去其中不合法的方案 我们直接算组成三角形的数量并不好算，因此我们可以反过来，先算出所有的选择，再减去其中不合法的方案 即 可 。 即可。 即可。

首 先 ， 在 网 格 的 所 有 点 中 任 取 三 个 点 的 方 案 数 为 ： C n ∗ m 3 首先，在网格的所有点中任取三个点的方案数为：C_{n*m}^3 首先，在网格的所有点中任取三个点的方案数为：Cn∗m3​

然 后 ， 再 减 去 所 有 不 合 法 （ 三 点 组 成 一 条 直 线 ） 的 情 况 ： 然后，再减去所有不合法（三点组成一条直线）的情况： 然后，再减去所有不合法（三点组成一条直线）的情况：
1 、 三 点 组 成 的 直 线 斜 率 为 0 （ 三 个 点 在 一 行 上 ） 的 情 况 ： n ∗ C m 3 （ 一 共 有 n 行 ， 每 行 上 有 m 个 点 ） 1、三点组成的直线斜率为0（三个点在一行上）的情况：n*C_m^3（一共有n行，每行上有m个点） 1、三点组成的直线斜率为0（三个点在一行上）的情况：n∗Cm3​（一共有n行，每行上有m个点）
2 、 三 点 组 成 的 直 线 斜 率 为 ∞ （ 三 个 点 在 一 列 上 ） 的 情 况 ： m ∗ C n 3 （ 一 共 有 m 列 ， 每 列 上 有 n 个 点 ） 2、三点组成的直线斜率为∞（三个点在一列上）的情况：m*C_n^3（一共有m列，每列上有n个点） 2、三点组成的直线斜率为∞（三个点在一列上）的情况：m∗Cn3​（一共有m列，每列上有n个点）

3 、 三 点 组 成 的 直 线 斜 率 不 为 0 和 ∞ 的 情 况 ， 这 时 的 斜 率 分 为 大 于 0 和 小 于 0 ， 因 为 这 两 种 情 况 是 对 称 的 ， 因 此 我 们 3、三点组成的直线斜率不为0和∞的情况，这时的斜率分为大于0和小于0，因为这两种情况是对称的，因此我们 3、三点组成的直线斜率不为0和∞的情况，这时的斜率分为大于0和小于0，因为这两种情况是对称的，因此我们 只 需 要 求 出 大 于 0 的 情 况 即 可 （ 小 于 0 的 方 案 数 与 大 于 0 的 方 案 数 相 等 ） 。 只需要求出大于0的情况即可（小于0的方案数与大于0的方案数相等）。 只需要求出大于0的情况即可（小于0的方案数与大于0的方案数相等）。
我 们 可 以 枚 举 网 格 中 所 有 低 为 i ， 高 位 j 的 斜 边 ， 该 边 的 两 个 端 点 为 三 角 形 的 两 个 点 ， 第 三 个 点 在 直 线 的 内 部 。 我们可以枚举网格中所有低为i，高位j的斜边，该边的两个端点为三角形的两个点，第三个点在直线的内部。 我们可以枚举网格中所有低为i，高位j的斜边，该边的两个端点为三角形的两个点，第三个点在直线的内部。
首 先 ， 这 样 的 直 线 有 ( n − i ) ∗ ( m − j ) 个 ， 每 条 直 线 内 部 第 三 个 点 的 选 择 方 案 数 为 g c d ( i , j ) − 1 。 首先，这样的直线有(n-i)*(m-j)个，每条直线内部第三个点的选择方案数为gcd(i,j)-1。 首先，这样的直线有(n−i)∗(m−j)个，每条直线内部第三个点的选择方案数为gcd(i,j)−1。

因 此 ， 对 于 每 一 个 ( i , j ) ， 其 方 案 数 有 ： ( n − i ) ∗ ( m − j ) ∗ ( g c d ( i , j ) − 1 ) 因此，对于每一个(i,j)，其方案数有：(n-i)*(m-j)*(gcd(i,j)-1) 因此，对于每一个(i,j)，其方案数有：(n−i)∗(m−j)∗(gcd(i,j)−1)

代码如下

#include 
#include 
#include 
#include 
#include 
#include