题目链接

思路:
三角形 = 三点不共线
求三角形个数 = 选择所有三点的方案(好算)- 三点共线的方案(不好算)
三点共线的方案 = 横着共线的方案(好算)+ 竖着共线的方案(好算)+ 斜着共线的方案(不好算)
其中,括号里写着好算的都是简单组合数。

那么现在来画图,在一个(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怎么算的?肯定不是数对吧?思路梳理还是得花心思。