题面
题解
考虑使用总数减去不合法的数量
首先将\(n, m\)都加上\(1\)，将网格变成坐标系
总数即为\(\large\binom{n\times m}{3}\)
不合法的有三种情况：
三个点在同一行上。每一行有\(\binom{m}{3}\)种不合法的情况，有\(n\)行，总数\(n\cdot\binom m3\)
三个点在同一列上。每一列有\(\binom n3\)种不合法的情况，有\(m\)行，总数\(m\cdot\binom n3\)
-
三个点在同一条斜线上
如果斜率为正，那么将一个点移动到原点，然后枚举另外一个点，这样的直线有
\((n - i)(m - j)\)条
然后斜率可能为负，\(\times 2\)即可
于是总数就是\(2\sum\limits_{i=1}^{n-1}\sum\limits_{j=1}^{m-1}(\gcd(i,j)-1)(n-i)(m-j)\)
于是答案为
\[\binom{n\times m}3 - n\binom m3 - m\binom n3 - 2\sum_{i=1}^{n-1}\sum_{j=1}^{m-1}(\gcd(i,j) - 1)(n - i)(m - j)
\]
\]
代码
结论题的代码就是好打
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define RG register
inline int read()
{
int data = 0, w = 1; char ch = getchar();
while(ch != '-' && (!isdigit(ch))) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();
return data * w;
}
inline long long C(int x) { return 1ll * x * (x - 1) * (x - 2) / 6; }
long long ans; int n, m;
int main()
{
n = read() + 1, m = read() + 1;
ans = C(n * m) - n * C(m) - m * C(n);
for(RG int i = 1; i < n; i++)
for(RG int j = 1; j < m; j++)
ans -= 2ll * (std::__gcd(i, j) - 1) * (n - i) * (m - j);
printf("%lld\n", ans);
return 0;
}