题目
思路
如果我们正面思考，直接求三角形个数是很难求得
但是，
我们将所有得到得三个点减去三点共线得数量不就是三角形的个数了？
所以考虑如何求
对于一个点和一条过这个点得直线
对于这条直线，只有上面点的横纵坐标同时为整数时才有用
假设这条直线的左端点为这条直线上x值最小的点
我们可以将这条直线平移，直到左端点为原点
对于直线上的点，一定有如下方程
\(\frac{x_2-x_1}{y_2-y_1}=\frac{x_3-x_1}{y_3-y_1}\)
x和y的取值不影响方程
将\(x_1==0\)并且\(y_1==0\)带入方程，
得到
\(\frac{x_2}{y_2}=\frac{x_3}{y_3}\)
接下来的事就是数出有多少个点满足
设当前这个点为\(x,y\)
得到递推式\(ans=(gcd(x,y)-1)*(n-x)*(m-y)*2\)
\(-1\)的意义在于要排除当前x，y这个点，
\(*2\)的意义在于对称
当然，以上的推到只是满足这是一条斜线，
当这条直线是水平方向或者竖直方向时，
我们发现根本不需要如此的麻烦
只需要减去\(C_{n}^{3}\)或者\(C_{m}^{3}\)就行了
ans的初始值也很简单，就是\(C_{n*m}^{3}\)
代码
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
using namespace std;
long long n,m;
long long ans;
long long solve(long long n,long long m)
{
long long ret=1;
for(int i=n;i>=n-m+1;i--)
ret*=i;
return ret/6;
}
int main()
{
cin>>n>>m;
n++;
m++;
ans=solve(n*m,3);
ans-=n*solve(m,3);
ans-=m*solve(n,3);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
ans=ans-(__gcd(i,j)-1)*(n-i)*(m-j)*2;
}
}
cout<<ans;
return 0;
}