思路与算法

网格有 $(m+1)(n+1)$ 个格点。先从中任取三个点，共 $\binom{(m+1)(n+1)}3$ 种，再减去共线的退化三点组。

水平共线为 $(n+1)\binom{m+1}3$，竖直共线为 $(m+1)\binom{n+1}3$。对非水平、非竖直的端点，设水平间隔 $dx>0$、竖直间隔绝对值 $dy>0$。两端点之间严格位于线段内部的格点有 $\gcd(dx,dy)-1$ 个。相同位移可平移 $(m+1-dx)(n+1-dy)$ 次，正、负斜率两种方向各有一份。因此再减

$$2\sum_{dx=1}^m\sum_{dy=1}^n(\gcd(dx,dy)-1)(m+1-dx)(n+1-dy).$$

程序用欧几里得算法逐位移求GCD，全部计数用64位整数，不取模。

正确性说明

任取三个不同格点，非共线时唯一形成三角形，共线时需要排除。水平与竖直三点组由所在行列唯一分类，互不重复。

其它共线三点组都有唯一的左右极端点，第三点严格在它们之间。把端点位移除以GCD得到最小整数方向，可知内部格点数恰为GCD减1。每个中间格点与所选极端点形成一个退化三点组；该组的极端点唯一，所以即使一条线上有更多格点，也不会重复扣除同一个三点组。平移计数和两种斜率恰覆盖所有非轴方向，故减去的正好是全部退化组，剩余为所有三角形。

复杂度

无大数组初始化，只用常数变量。共 $mn$ 个正位移，每次Euclid耗时 $O(\log(\min(m,n)+1))$，总时间 $O(mn\log(\min(m,n)+1))$，额外空间 $O(1)$。组合数和轴向计数为常数时间。

易错点

1. $m\times n$ 是格子数，点数是 $(m+1)(n+1)$，样例2×2有9个点。
2. 位移两端之间有GCD减1个内部点，不能用GCD本身。
3. 两种斜率乘2，水平和竖直另算；循环里不把位移0也纳入。
4. 输出精确计数而非取模。最大点数为1002001，三项相乘中间量约 $1.01\times10^{18}$，仍需64位并先提升类型。
5. 覆盖1×1、瘦长网格和1000×1000。独立答案以totient恒等式重排位移和，并与25个小网格的全部三点叉积枚举核对。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int gcdValue(int a, int b) {
    while (b) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}
ll choose3(ll n) {
    return n < 3 ? 0 : n * (n - 1) * (n - 2) / 6;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n;
    cin >> m >> n;
    ll points = (m + 1LL) * (n + 1);
    ll answer = choose3(points) - (n + 1) * choose3(m + 1) - (m + 1) * choose3(n + 1);
    for (int dx = 1; dx <= m; dx++)
        for (int dy = 1; dy <= n; dy++)
            answer -= 2LL * (gcdValue(dx, dy) - 1) * (m + 1 - dx) * (n + 1 - dy);
    cout << answer << '\n';
}