ACM - CQOI - 数三角形 - 数学 - 容斥原理
思路：
三角形 = 三点不共线
求三角形个数 = 选择所有三点的方案（好算）- 三点共线的方案（不好算）
三点共线的方案 = 横着共线的方案（好算）+ 竖着共线的方案（好算）+ 斜着共线的方案（不好算）
其中，括号里写着好算的都是简单组合数。
那么现在来画图，在一个（n，m）的矩形之中，什么情况下连接主对角线和副对角线，会发生三点共线的情况？
如图所示，红色箭头标注的线上就会存在三点共线。（注意，这是副对角线，左下、右上）
结论（1）：
在（n，m）矩形之中，主、副对角线存在对称性，所以算一个就好，答案×2
结论（2）：
（n，m）矩形什么情况下，存在主、副对角线中三点共线情况？
gcd(n,m)>1。
可以正面思考：gcd(n,m)>1时，令k=gcd(n,m)，则可知最小的矩形的比例其实为(n/k, m/k)，所以把这个小矩形的对角线一直延长，由相似性可知，既然过了(n,m)，也会过1(n/k, m/k)、2(n/k, m/k)、等等点，这是按比例来的。
可以反面思考：gcd(n,m)=1时，说明(n,m)互斥，互斥的点之中，在(0-n)与(0-m)的序列之中，不可能出现等比例的缩放问题。
结论（3）：
（n，m）矩形当中，怎么去重斜线？
步骤（1）：枚举（n，m）矩形当中的所有的小矩形，即长宽从1-n，1-m来枚举。
步骤（2）：在（n，m）矩形之中，对于固定长宽的小矩形（i，j），这样的小矩形有多少个？
画画图，从左上角（0，0），右下角（i，j）开始。
从左到右，可以从（i，j）平移到（i，m），共有 m+1-j 个
从上到下，可以从（i，j）平移到（n，j），共有 n+1-i 个
所以乘法原理
结论（4）：在（n，m）矩形之中的固定长宽的小矩形（i，j），贡献度是多少？
注意！！！注意！！！这里的坑点很大。因为，我们已经固定了这个小矩形，所以要求这个（i，j）矩形的贡献度，在选共线三点的时候，一定要选择最远的两点和中间的某一点（如果不选最远的两点，那么这个矩形则不是定义中的（i，j）的矩形）。在这个选择中，对角线总点数是 gcd(i,j) + 1，去掉最远两点，剩下可选点是 gcd(i,j)-1 个。
所以，综上所述，问题解决。代码其实没几行。
（吐槽：斜线画直了好难）
#include<bits/stdc++.h>
using namespace std;
int m, n;
long long Cn3(int x){
return 1LL * x * (x - 1) * (x - 2) / 6;
}
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int main(){
scanf("%lld%lld", &m, &n);
long long ans = Cn3((n+1) * (m+1)) - (m+1) * Cn3(n+1) - (n+1) * Cn3(m+1);
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
if (gcd(i, j) > 1)
ans -= 2 * (gcd(i, j) - 1) * (m + 1 - i) * (n + 1 - j);
printf("%lld\n", ans);
return 0;
}
补充说明：
这个题入手最大的问题其实是：数据样例很小且组数很少。
比如n=m=1时，答案显然为4.
但是，n=1，m=2时，这个答案是多少？怎么做到不重复不遗漏？
n=m=2时，答案为76怎么算的？肯定不是数对吧？思路梳理还是得花心思。
