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

下面这份解析，试图在有限篇幅内尽量深度剖析本题的核心思路与代码实现背后的推理与证明，力求展现其中最关键的数学本质。为便于说明，以下所提到的“n×m 网格”指的是“(n+1)×(m+1) 个格点”的集合——因为若在坐标轴上从 0 到 n 和 0 到 m 画线，那么水平方向有 n+1 条网格线、竖直方向有 m+1 条网格线，共有 (n+1)×(m+1) 个离散格点。代码中正是将输入的 n、m 各自加 1，来对应这种“点的数量”而非“格子的数量”。

一、问题回顾

题意：给定一个 n×m 网格（实际有 (n+1)×(m+1) 个格点），求取所有三点都在格点上且不共线的三角形总数。

• 若格点总数为 $N$，那么任选 3 个点有 $\binom{N}{3}$ 种组合。
• 但题目要求“不能三点共线”，因此需要从总的 $\binom{N}{3}$ 中减去所有“共线”的三点组合数。

代码中：

cpp
n ++, m ++ ; // n、m 各加 1 后，(n, m) 分别变为 (n+1, m+1) 条网格线 => (n*m) 格点。

于是格点总数为 $n \times m$。下面主要讨论“共线三点”如何统计和扣除。

二、第一步：总的三点组合数

总的格点数是 $n \times m$。从中任选 3 点的组合数为

代码中用

cpp
LL C(int n) { 
    return (LL)n * (n - 1) * (n - 2) / 6; 
}

来计算组合数，记为 C(n*m)。

三、第二步：扣除共线情况

1. 水平线与竖直线上共线的三点

1）水平线上的共线三点

• 水平方向共有 $n$ 行(实际上是 n 行“带点的水平线”，因为加 1 后有 n 条水平方向可选)，每一行都有 $m$ 个点。
• 在同一行上，任意 3 个点共线，因此每一行上的共线三点数就是 $\binom{m}{3}$。
• 共计 $n$ 行，所以总共有

个在水平线上共线的三点组合。

2）竖直线上的共线三点

• 竖直方向共有 $m$ 列，每一列上有 $n$ 个点。
• 同理，每列上的共线三点数是 $\binom{n}{3}$。
• 共计 $m$ 列，所以总共有

个在竖直线上共线的三点组合。

在代码中，对应这两项之和：

cpp
- (LL)n * C(m) - (LL)m * C(n)

这里的 C(m) 就是 $\binom{m}{3}$，C(n) 就是 $\binom{n}{3}$。

2. 斜线上的共线三点

这里只是“水平 + 竖直”还不够，因为还存在大量具有不同斜率的直线也可能包含 3 个及以上的格点。比如斜率为 1、2、1/2、-1 等，各种有理斜率都需要考虑。

（1）为什么要用 gcd(i, j) 计算

令某条线在网格中沿“向右下”的方向走（当然也可以向右上，这里做对称处理时会乘以 2 ）。若一个方向向量为 $(i, j)$，表示如果你从某个格点 $(x,y)$ 出发，向右下走 $i$ 步纵向、$j$ 步横向，就还在格点上。

• 若 $\gcd(i, j) = 1$，说明步长是“最简方向”。沿这个方向只要走一次就跳到相邻的格点，无法在两个“跳跃”之间再插入别的格点。
• 若 $\gcd(i, j) = d > 1$，可以把 $(i, j)$ 写成 $(d \cdot i_0,\; d \cdot j_0)$，其中 $\gcd(i_0, j_0) = 1$。这意味着沿 $(i, j)$ 方向实际上可以在中间再细分：$(i_0, j_0)$、$(2\,i_0,2\,j_0)$、…、$(d\,i_0, d\,j_0)$。也就是说，向量 $(d\,i_0, d\,j_0)$ 在这条线上至少可以容纳 $d+1$ 个格点（若区间足够长的话），自然就包含了很多三点共线的组合。

因此，能在同一直线上形成三点共线的关键在于：这条线上是否至少有 3 个格点。而如果某个方向向量 $(i, j)$ 能在网格内放大或平移后给出多于 2 个格点，就会贡献若干共线三点。这里的计数核心是：

• $\gcd(i, j) - 1$ 就表示当你采用向量 $(i, j)$ 时，在 $(0,0)$ 到 $(i,j)$ 的这一段直线上，实际还有 $\gcd(i,j)-1$ 个内部点。若 $\gcd(i, j) \ge 2$，那么该方向本身一次走就能包含至少 3 个格点 (起点、若干中间点、终点)。
• 网格中除了 (0,0) 出发这条线，还可以从其它起点出发，同样会形成若干共线点。

（2）为什么遍历 i=1..n, j=1..m

在代码中

cpp
for (int i = 1; i <= n; i ++ )
    for (int j = 1; j <= m; j ++ )
        res -= 2ll * (gcd(i, j) - 1) * (n - i) * (m - j);

• 遍历所有 $(i, j)$，意为“斜率 = j / i” 或其镜像方向；这里 (i, j) 不含 0，是为了不跟水平/竖直搞混。
• $\gcd(i, j) - 1$ 就是说明若此方向有 “$d-1$” 个中间点，则会在网格中形成很多包含 3 个及以上格点的直线需要扣除。

最关键的部分在于乘积 $(n - i)\times(m - j)\times 2$：

• $(n - i)$ 表示在竖直方向上，有多少种办法把这条线往下平移（或往上平移）而仍然保持在网格内部。例如，如果你的方向向量是 $(i, j)$，那么你最多只能把起点放到行数 $\le n-i$ 的那些行上，才能保证再走 $i$ 步不会越界。
• $(m - j)$ 类似道理，水平方向能平移的次数。
• 乘以 2 是因为不只是“向右下”一种，还可以“向右上”，或整体翻折；从几何上看，不同斜率 $\pm \frac{j}{i}$ 都需要扣除，而这里通过乘 2 一次性考虑了“正斜率”和“负斜率”的情形。

由于 $\gcd(i, j) - 1$ 正比于该方向上多出来的“内部点个数”，每次就对应若干三点共线的组合要减去。最终，这部分用

cpp
res -= 2ll * (gcd(i, j) - 1) * (n - i) * (m - j);

实现。

（3）为什么是乘 “($\gcd(i, j)-1$)\cdot(\text{可平移次数})” 而不是直接三点组合

这里要注意，它并非直接用 $\binom{d+1}{3}$ 的方式；因为我们是统计“额外多出的三点”，或说“由于有 $\gcd(i, j)-1$ 个中间点才产生的那些三点组合”。该部分推导相对更繁琐，但可以理解为：

• 方向向量若是最简 (i.e. $\gcd(i,j)=1$)，则在线段起点和终点之间不会多出额外点，不会额外产生 3 个及以上的共线点，“额外的”共线三点为 0。
• 一旦 $\gcd(i,j)>1$，那么每次在这条直线上，就多了 $\gcd(i,j)-1$ 个可插点，继而可以形成三点共线。
• 这些线都可以进行平移：只要平移不超出网格边界，就会出现新的可导致三点共线的直线。

把所有这样的情况累积起来，就是上式循环所做的事。

四、整体公式与代码逻辑

因此，最终的计算公式为：

代码中：

cpp
// 1) 全部三点组合
LL res = C(n * m);

// 2) 水平 + 垂直的共线三点
res -= (LL)n * C(m);
res -= (LL)m * C(n);

// 3) 各种斜线上的共线三点
for (int i = 1; i <= n; i ++ )
    for (int j = 1; j <= m; j ++ )
        res -= 2ll * (gcd(i, j) - 1) * (n - i) * (m - j);

输出 res 即为所求的“不共线三点”所构成的三角形数量。

五、核心思路的证明要点

1. 三角形总数的起点：$\binom{nm}{3}$
   三个点均在 $(n \times m)$ 个格点上，每 3 点一组即可。

2. 扣除水平方向和竖直方向的共线三点

   • 每行有 $m$ 点，一行上能选出 $\binom{m}{3}$ 个三点共线；共有 $n$ 行，因此减去 $n\binom{m}{3}$。
   • 每列有 $n$ 点，一列上能选出 $\binom{n}{3}$ 个三点共线；共有 $m$ 列，因此减去 $m\binom{n}{3}$。

3. 扣除更一般斜率的共线三点

   • 所有斜率可视为“向量 $(i,j)$”所代表的方向。只要 $\gcd(i,j)>1$，意味着在段 $(0,0)$ 到 $(i,j)$ 中插入了若干格点，从而一次性在这条方向上就可能出现至少 3 个点共线。
   • 把 $(i,j)$ 从所有可能的 $(1\le i \le n,\; 1\le j \le m)$ 扫过后，再乘以可平移的次数 $(n-i)(m-j)$，同时要考虑正反两种斜率，因此乘以 2。
   • “$\gcd(i,j)-1$”反映了在一段向量中多出来的内部点数量，由此产生了那些要被扣除的“多余”三点共线组合。

4. 可行性的隐式保证
   在网格范围内，每条平移后的线不会彼此重复统计或漏统计，核心是“向量最简”与“gcd > 1”之间的相互关联，以及“(n-i)(m-j)×2”对应所有平移与镜像方向的完整覆盖。该部分在许多经典“网格点共线统计”题中是标准做法。

六、总结

从最初的总组合 $\binom{nm}{3}$ 出发，先减去显而易见的水平方向与竖直方向的共线组合，接着用 $\gcd(i,j)$ 的方法统一处理所有具有不同斜率的直线，从而排除所有剩余的共线点集。这里最有“妙手”的地方在于那段双重循环里，用 $\gcd(i,j)-1$ 与 $(n-i)(m-j)\times2$ 相乘来一次性覆盖所有“斜率非 0、非无穷”的情形，实现了对剩余共线三点的扣除。

该思路简洁优雅，且复杂度约为 $\mathcal{O}(n\,m\log\max(n,m))$（主要来自 $\gcd$ 计算），在 $n,m \le 1000$ 的数据范围内完全可行，输出即为“不共线三点”构成的三角形数量。

以上便是代码背后最核心的推理过程和公式推导要点。整个思路的关键一环在于：

• 先求总三点组合；
• 再剥离各类共线情况（水平、竖直、斜线），其中斜线部分用 $\gcd$ 技巧统计。

这也是网格三角形计数中常见的“全体 - 共线”框架，将所有可能的共线情形剖分并各个击破，从而得到最终答案。

下面这份答复会以“你提出的疑惑和思路”为脉络，从根本处厘清几大常见困惑，并解释为什么代码中用的

确实能正确扣除所有斜线共线的三点组合，从而与实验结果（例如 3×3 网格得 76）相符。

为了对齐表述，下文仍遵循代码的约定：

• 输入的 n,m 在读入后自增 1，故实际网格点数量是 $(n)\times(m)$。
• 整个循环中 i 的范围是 $[1,n]$，j 的范围是 $[1,m]$。
• 最终我们要数的是：从这 $n \times m$ 个格点中选 3 点、且不共线的三角形个数。

1. 关于水平、竖直共线的部分

这一段你已经很清楚：

• 水平共线：每一行上有 $m$ 个点，可选出 $\binom{m}{3}$ 个三点；共有 $n$ 行，故总共线数 $= n\cdot\binom{m}{3}$。
• 垂直共线：每一列上有 $n$ 个点，可选出 $\binom{n}{3}$ 个三点；共有 $m$ 列，故总共线数 $= m\cdot\binom{n}{3}$。

在代码里体现为：

cpp
res = C(n*m)  // 所有三点组合
    - n*C(m)  // 扣除水平
    - m*C(n); // 扣除竖直

2. 关于斜线共线的核心困惑

2.1 gcd(i,j)=d 对应多少“线上 3 点”？

你注意到：

• 若在“最小段”里有 $d+1$ 个点，则该最小段上恰有 $\binom{d+1}{3}$ 组三点。比如 $d=4$ 时，最小段有 5 个点，对应 10 组三点 ($\binom{5}{3}=10$)。
• 而代码中写的却是 $$\texttt{(gcd(i,j)-1)}$$ 甚至还乘以 2，有时看起来跟 $\binom{d+1}{3}$ 不一致。比如你举了 $d=4$ 时 $\binom{5}{3}=10$ 而 $2\times(4-1)=6$ 并不相等。

这让人产生“是不是代码漏减或少减”的担忧。实际上并不矛盾，根本原因在于：

当 gcd(i,j)=4 时，你在代码循环的“i=4, j=4” 这一档里并不是在扣除那条方向等价于(1,1)延伸 4 步的整条长线上的所有三点组合。因为对应斜率 = 1 这件事，在其他 (i,j) 比如 (1,1)、(2,2)、(3,3) 的循环档次中，也会各自扣除相应的部分。
换言之：代码做的是“把所有可能的 collinear 三点拆分到各个 gcd 分层”去计数，然后总和**恰好覆盖全部共线组合。不是说 (i=4,j=4) 这一次就要负责把“整条含 5 个点的大线”所有三点一次扣完。

打个比方：

• 当斜率 = 1 时，它对应的 $(i,j)$ 有 $(1,1),(2,2),(3,3),(4,4),\dots$ 等等，每个都落入循环一次。
• 其中 $\gcd(1,1)=1$，$\gcd(2,2)=2$，$\gcd(3,3)=3$，$\gcd(4,4)=4$，$\dots$。
• 这些循环档位合在一起，把所有那条“斜率=1”的可能长短线段上的三点共线都扣除了，而且不会重复也不会缺失。

所以，你看到的 d=4、“(4-1)=3 与 10 不相等”的矛盾，只是一眼看过去觉得“扣得不够”，但实际上还有 d=1,2,3 时的那几档会一起分担/覆盖该方向上的共线点，一起把合计的 $\binom{5}{3}=10$ 扣完。代码里的写法正是这样利用了 (gcd(i,j)-1) 的分层思路，逐一累加(或累减)到最终恰好。

简而言之：循环遍历到 $(i,j)$ 只是“扣除那些基于步长 = (i,j) 的最短子段”中出现的多余三点。而“更长子段”中的多余三点，会在更小 gcd 的档位(或同一 gcd 的不同 i,j)里被扣除。
这是一种“打散后再汇总”的计数方式，因此它与“直接对一条完整线段做 $\binom{k}{3}$ 统计”在数值上是一致的，但拆分得更细，分多次处理。

2.2 为什么公式正好是 2×(gcd(i,j)-1)×(n-i)×(m-j)？

理解了上面的“分层”大前提，就明白 (gcd(i,j)-1) 并不是单纯代表“该线段上一口气能选出多少组三点”，而是“在 gcd=d 时，这条最小步长里多出来的点所引发的 ‘新增’ 3 点组合数”，并且再乘以“可平移次数 × 2(正负方向)”。

• (n - i) ：在竖直方向能把这条线段往上/往下平移多少次（更准确说：起点能选多少行）。如果你要走 i 步竖直，那么起点的 row $\le n-1 - i$；加上坐标从 0 计到 n-1，共能放 $(n-1 - i)+1 = n-i$ 个起点行数。
• (m - j) ：同理，水平方向能平移的次数。
• 乘 2 ：考虑斜率是 $\pm \frac{j}{i}$ 两种方向（向右上或向右下）。

最终，这个表达式就可以把所有 gcd>1 的方向、所有能放置的平移情况“一网打尽”。它不会重不不会漏，是一个经典做法。

3. 为什么小例子验证没问题

你举了 $n=2,m=2$ 这组输入（其实加 1 后变为 $n=3,m=3$，即 3×3=9 点），算出 76。

• 总三点组合：$\binom{9}{3}=84$。
• 水平共线：3 行，每行 3 点，$\binom{3}{3}=1$；共 3×1=3。
• 垂直共线：3 列，同理 3。加起来 6。
• 还剩 84-6=78。
• 真正不共线的答案是 76，所以需要再扣 2 条对角线。对角线各有 3 点=>各提供 1 组三点，共 2。
• 这样就正好 76。

代码里：当 $n=3, m=3$

1. 遍历 (i,j) = (2,2) 时，$\gcd(2,2)=2$，贡献 = $$2 \times (2-1)\times (3-2)\times (3-2) = 2\times1\times1\times1=2.$$ 它正好对应那两条主对角线（$+$负斜率），各扣 1 条。
2. 其它 (i,j) 要么 gcd=1 => (gcd(i,j)-1)=0，要么 (n-i)=0 或 (m-j)=0 => 平移次数=0，所以没有额外贡献。
3. 因而总斜线扣除 = 2，和我们手动数的那 2 条对角线吻合。

4. 再看一个 gcd 较大时的直观说明

假设有更大的网格，比如 7×7 点(即输入 n=6,m=6，再加 1 变 7×7)。那里面斜率=1 的线可以很长(多达 7 个点一条对角)。但在代码中会被 (i=6,j=6) gcd=6、(i=5,j=5) gcd=5 … 以及 (i=1,j=1) gcd=1 等各自分块扣除。大致地：

• gcd=1 处理了“(1,1) 最短段”引起的部分；但那并不等于一次性把 7 点对角全部 $\binom{7}{3}$ 扣掉。
• gcd=2 处理了能拆成 2 步的那种 “(2,2) 最短段”。
• gcd=3,4,5,6 同理。

各档位加在一起，就能保证把所有斜率=1 的线段上的三点扣完，也把斜率=1/2、2、3、等所有非 0 非无穷的斜率都扣完。

5. 结论：代码的分层思路是正确且常见的

1. 先减掉水平 + 垂直共线
2. 再减所有 gcd>1 的斜率共线
   • 通过双层循环遍历 $(i=1..n, j=1..m)$。
   • 每对 $(i,j)$ 用 2*(gcd(i,j)-1)*(n-i)*(m-j) 扣除它所对应的那一部分“额外出现的 3点共线”。

表面看 (gcd(i,j)-1) 并非直接等于 $\binom{d+1}{3}$，但它配合“代码实际上对所有 gcd=1..(大值) 进行多次循环”这一事实，最终能够把所有存在于网格里的斜线共线组合恰当扣除，一点不多，一点不少。

你在思路中提及的矛盾（如 “d=4 时 $\binom{5}{3}=10$ 与 2×(4-1)=6 不一致”）其实是因为把‘(i=4,j=4) 这一档要扣除的全部’误解成‘整条包含 5 个点的线段的全部三点’。事实上，“包含 5 个点的大线段”在循环里会被 gcd=1,2,4 等多档次合力扣完，所以最终才能与手动数的结果一致。

6. 小结

• 问题：三角形总数 = $\binom{nm}{3}$ - (共线三点数)。
• 共线三点分解为：
  1. 水平：$n\cdot \binom{m}{3}$，
  2. 竖直：$m\cdot \binom{n}{3}$，
  3. 斜线：由循环 $$\sum_{i=1}^n \sum_{j=1}^m 2\,\bigl(\gcd(i,j)-1\bigr)\,(n-i)\,(m-j)$$ 扣除。
• 这个斜线部分的公式并不是一次直接把整条线上的 $\binom{d+1}{3}$ 扣完，而是把所有线段可能的共线分布到了多重 gcd(i,j) 档里“分别扣”；对每个方向只减掉那部分 “额外产生的中间点贡献”(= gcd-1)，然后再和别的 gcd 档位“合并贡献”后，正好与完整直观的 $\binom{k}{3}$ 计数吻合。

因此，你在“(gcd(i,j)-1)”和“$\binom{d+1}{3}$”之间反复对比时，只要记住代码的循环是会重复多档 gcd 归类，不是仅仅 i=4,j=4 一次就干完 d=4 这条方向的所有事，就能理解它们怎么严丝合缝地拼合成完整扣除数目。

这也正是为什么这个方法常被用于网格共线题：把复杂的“同一直线上 3+点”问题，拆成 gcd 不同步长的最小段汇总，多次循环后凑出正确的总共线数，简洁而有效。

希望以上分析能够拨开你在思路中遇到的“(gcd-1) 和 $\binom{d+1}{3}$ 关系”疑团，也能解释为什么当 d=4 等更大 gcd 时，代码与手动想象会表面“看似不一致”，但合计起来并没有缺失或多扣。

一句话：

代码并非“单次就扣完整条大线”，而是分多次把大线上的共线逐块扣掉，并在所有 gcd(i,j) 循环中达成总和正确。

下面给出一个**“按你自己的思路”**去实现的示例框架，力图直接地、更加“显式”地统计每条斜线上的三点共线数目，从而与“总组合数”做减法。换言之，我们会：

1. 先从 $\binom{N}{3}$（其中 $N=n\times m$）减去水平和竖直共线；
2. 再显式枚举所有「互质方向」$(a,b)$（即 $\gcd(a,b)=1$，且不含 $a=0$ 或 $b=0$ 的情形），对每一个方向，遍历所有可行起点，计算“该起点沿方向可排出的点数目 $k$”，然后把 $\binom{k}{3}$ 加起来，作为需要扣除的三点共线数量。

最后得到的结果，必然与原代码等价（两种方法只是实现思路不同，数学结论一致）。不过需要注意，这套“显式遍历所有斜线”的写法往往时间复杂度更高；在 $n,m\le 1000$ 时还算能勉强跑（需仔细优化），再大就会比较吃力。

一、思路概述

1. 令 $\text{total} = \binom{n\times m}{3}$，这是从 $n\times m$ 个点中随便选三点的组合总数。

2. 扣除水平三点共线：$n \times \binom{m}{3}$。

3. 扣除竖直三点共线：$m \times \binom{n}{3}$。

4. 扣除斜线三点共线：

   • 只考虑正斜率（$b>0$）的最简方向 $(a,b)$（即 $\gcd(a,b)=1$），统计其所有线段的三点共线数，然后再乘以 2（对应正斜率和负斜率）。
   • 对于每个互质 $(a,b)$，我们在网格中枚举所有可能的起点 $(x_0,y_0)$。能走多少步 $t$ 使得 (x_0 + t*a, y_0 + t*b) 仍在网格边界内？若最大可走步数为 $t_{\max}$，则该线段包含 $t_{\max}+1$ 个格点；若 $\ge 3$，就有 $\binom{t_{\max}+1}{3}$ 组三点共线。把它们累加即得到该方向在整个网格中产生的共线三点总数。
   • 将对所有 $\gcd(a,b)=1$ 的 $(a,b)$ 做求和，然后乘以 2 扣除（兼顾向上/向下两种斜率）。

5. 最终得到的结果即为“不共线的三角形数”：

   $$\text{res} = \binom{nm}{3} - n\,\binom{m}{3} - m\,\binom{n}{3} - 2 \times \Bigl(\text{所有正斜率方向的共线三点和}\Bigr).$$

这就是一个“你所设想的显式做法”。

二、关键实现点

1. 处理输入并加 1

与原题一致：题目给的 n,m 其实是“格子”数，要得到点的行列数都要 n++、m++。这样最终网格有 $n \times m$ 个格点。

cpp
cin >> n >> m;
n++, m++; 
// 现在真正的点数是 n*m

2. 计算组合数 $C(n,3)$

cpp
// 计算 nC3 的小函数
long long C3(long long x) {
    // 注意溢出，最好用 1LL*x*(x-1)*(x-2)/6
    if (x < 3) return 0;
    return x*(x-1)*(x-2)/6;
}

3. 水平/竖直共线数量

cpp
long long total = C3(1LL*n*m); 
// 全部三点组合

long long horiz = (long long)n * C3(m); // 水平
long long vert  = (long long)m * C3(n); // 竖直

long long ans = total - horiz - vert;

4. 正斜率方向的三点共线统计

我们只要考虑 $1 \le a \le n-1,\; 1 \le b \le m-1,\; \gcd(a,b)=1$。

• 为什么到 n-1、m-1？因为如果方向步长 a = n 或 b = m，那走一步就出界了，没有更多点可走。
• $\gcd(a,b)=1$ 保证这是“最简方向”，不重复统计相同斜率下的倍数方向。

对每个最简方向 $(a,b)$：

• 遍历每个起点 $(x_0,y_0)$，其中 $0 \le x_0 \le n-1,\; 0 \le y_0 \le m-1$。
• 计算在该方向上能走的最大 $t$ 使 $(x_0 + t\cdot a) \in [0,n-1]$ 且 $(y_0 + t\cdot b) \in [0,m-1]$。于是 $$t_{\max} = \min\Bigl(\lfloor\frac{n-1 - x_0}{a}\rfloor, \;\lfloor\frac{m-1 - y_0}{b}\rfloor\Bigr).$$
• 该线段含 $t_{\max} + 1$ 个点 => 三点共线数 $\binom{t_{\max}+1}{3}$。若 $t_{\max}<2$ 则为 0，不计。

把所有起点的结果加起来，就得到斜率 = $\frac{b}{a}$ 时的共线三点总数 diag_current。再把它累加到 diag_sum 里。

最后，我们把 diag_sum 乘以 2，再从 ans 中减去，就完成了对斜线三点的扣除。

伪代码示例

cpp
long long diag_sum = 0;
for (int a = 1; a < n; a ++) {
    for (int b = 1; b < m; b ++) {
        if (gcd(a,b) == 1) {
            // 枚举所有起点
            long long cnt = 0; // 本方向产生的三点共线总数
            for (int x0 = 0; x0 < n; x0 ++) {
                for (int y0 = 0; y0 < m; y0 ++) {
                    // 能走多少步 t
                    int max_t_x = (n-1 - x0)/a; // 注意整除
                    int max_t_y = (m-1 - y0)/b;
                    int t_max = min(max_t_x, max_t_y);
                    if (t_max >= 2) {
                        cnt += C3(t_max + 1);
                        // 线段上有 (t_max+1) 个点 => 组合数
                    }
                }
            }
            diag_sum += cnt;
        }
    }
}

// 乘以 2 (因为还有负斜率)
ans -= 2LL * diag_sum;

这样就显式地把所有正斜率的线都找了一遍，每条线段上若有 $k\ge 3$ 个点，便扣除 $\binom{k}{3}$。

三、复杂度和优化

上面这段伪代码的三重循环：

• $a$ 最多 $n$ 次，
• $b$ 最多 $m$ 次，
• $(x_0,y_0)$ 又是 $n \times m$ 次，

整体是 $\mathcal{O}(n^2 m^2)$ 级别，若 $n,m$ 都到 1000，则达到 $10^{12}$ 次循环，显然过大。所以若你真这样写，可能很难在合理时间内跑完。

1. 能否减少内层循环？

我们发现：

可以尝试用前缀和或积分几何之类技巧来快速求。如果你有兴趣做更深层的数学推导，可以把

视为某种分段函数，再叠加 $\lfloor\frac{m-1-y_0}{b}\rfloor$，做二维枚举的合并。但实现起来相对复杂，不是几行代码能搞定。

2. 进一步思路

• 若只是要验证正确性，在小范围（比如 $n,m \le 50$）上，这样的显式做法绝对能跑出和原代码相同结果。
• 若要在 $n,m\le 1000$ 都通过，还要进一步进行数学化简或充分剪枝，或借助一些更巧妙的求和公式。否则确实会超时。

这就是为什么比赛或实际算法中，更常用那种分 gcd 层计数(即原代码的做法)，复杂度只要 $\mathcal{O}(nm\log\max(n,m))$ 就能搞定，并且公式短小、实现简单。

四、总结

1. 你的思路（先减水平方向和竖直方向，再对每个斜率把所有线段的 $\binom{k}{3}$ 显式累加）完全可以实现，也能得到与原代码相同的结果，数学上是一致的。
2. 实现示例：上面给了伪代码框架；若要写成完整 C++，只需把 gcd、C3 函数、输入输出、以及循环等拼合到一起即可。
3. 时间复杂度：如果不做任何优化，三重循环会非常大（$n^2 m^2$ 量级），在 $n,m=1000$ 时大概率跑不完；若只是演示正确性或在较小数据下使用，这种方法是最直观的。
4. 为什么原代码不这么写：它用 $$\texttt{res -= 2*(gcd(i,j)-1)*(n-i)*(m-j)}$$ 来“一步到位”统计所有斜线共线，实际上是“拆分到 gcd 层+最短段”的方式，少了两层循环，效率极高。

结论：若你想“改写”成显式数所有斜线，就可以按照上面伪代码的思路做。但请注意到大规模时的性能瓶颈，以及如果要在实际大输入上跑，最好做更多数学/数据结构优化来降低复杂度。

在这道题里，$\gcd(i,j)$（即 $i$ 与 $j$ 的最大公约数）最核心的作用是：它能够准确地告诉你，沿着“步长”(i,j)走时，中间会不会再经过额外的格点。

• 若 $\gcd(i,j)=1$，说明 $i$ 与 $j$ 互质，从某个起点出发、按向量 $(i,j)$ 只走一步，就不会再在两端之间多插出别的网格点。换言之，(i,j) 是一个“最简方向”——除起点和终点外，没有“中间格点”。

• 若 $\gcd(i,j)=d>1$，我们就可以把 $(i,j)$ 写成 $d\cdot(i',j')$，其中 $i'$ 和 $j'$ 互质。这样，从某个格点出发，沿 $(i,j)$ 的那一小段线上会出现“额外的 d-1 个内部格点”。例如：

  • $i=6,\,j=4$，$\gcd(6,4)=2$，则 $(6,4)=2\cdot(3,2)$。走一大步 $(6,4)$ 其实可以拆成连着走两步 $(3,2)$。那么在这“一大步”的首尾之间，就会出现一个额外的格点（即走一步 $(3,2)$ 时的位置）。
  • 当有了这些“额外的中间点”，就可能出现至少 3 个点共线的情况；所以凡是 $\gcd(i,j)>1$ 的方向，都要扣除那些由于“额外中间点”而产生的三点共线。

简言之，$\gcd(i,j)$ 不仅仅是求最大公约数的函数；在网格几何里，它还能告诉我们：“这个方向步长里究竟有多少‘中间格点’可插入”。一旦 $\gcd(i,j)>1$，意味着会在同一直线上出现 3 个或更多点共线，需要相应扣除。