Description
给定一个 的网格，计算三个点都在格点上的三角形共有多少个。三角形的三点不能共线。
Solution
记这个题在这里就是为了记一句话：
「枚举两个顶点是四次方的。但实际上我们大多数时候并不在意两个顶点的具体坐标，而只关心两点的相对坐标差。枚举横纵坐标差就是平方的，极大优化了复杂度。」
一直就觉得枚举两个顶点这样一个简单的操作居然是 次方极其不便
然后这个题就很简单了。枚举横坐标差/纵坐标差，那么斜线上的三点共线数量为
总方案减去就行了。
然后也可以用数论函数的知识，将后面的 拆成欧拉函数的形式。可以做到 。
Code
#include <bits/stdc++.h>
using namespace std;
long long n, m;
int gcd(int a, int b){
return !b ? a : gcd(b, a % b);
}
int main(){
cin >> n >> m;
++n, ++m;
long long ans = n * m * (n * m - 1) * (n * m - 2) / 6;
ans -= m * n * (n - 1) * (n - 2) / 6;
ans -= n * m * (m - 1) * (m - 2) / 6;
for(int i = 1; i < n; ++i)
for(int j = 1; j < m; ++j)
ans -= 2ll * ((n - i) * (m - j) * (gcd(i, j) - 1));
cout << ans << endl;
return 0;
}