BZOJ 3505 数三角形

题意

在n*m的网格中有多少个顶点在网格上的三角形

数据范围

$$n,m\leqslant1,000$$

题解

n*m个点中任选三个有C(n+m,3)种选择，在同一行的或同一列的直接算组合数减。对于斜线上的点，有如下做法：

• (x,y)和(a,b)所成线段中的点数共有gcd(x-a,y-b)+1个（包括两端）。
• 现在把端点坐标减去(a,b)，就成了(x,y)与(0,0)所成线段，那么长度相同的线段答案就可以相乘
• 与它长度相同的线段有2(n-x)(b-y)个（镜面方向还有一倍）
• 

  代码

#include<cstdio>
int gcd(int x,int y) {if (y==0) return x; return gcd(y,x%y);}
long long C(long long x)
{
	return x*(x-1)*(x-2)/6;
}
int main()
{
	int n,m,tmp;
	scanf("%d%d",&n,&m);m++,n++;
	long long ans=C(n*m)-C(n)*m-C(m)*n;
	for (int i=1;i<n;i++)
	for (int j=1;j<m;j++)
	{
		tmp=gcd(i,j)+1;
		if (tmp>2) ans-=(tmp-2)*2*(n-i)*(m-j);
	}
	printf("%lld",ans);
	return 0;
}