BZOJ 3505 [Cqoi2014]数三角形

题目大意

给定一个nxm的网格，请计算三点都在格点上的三角形共有多少个。

容易想到这题可以用所有可能的选定三个点的方案减去不合法的点，所以此题就变成了求三点共线的方案个数。

水平垂直的很好处理，重点是''和'/'的三点共线方案。

只讨论'/'的方案，因为''的方案个数与其相同。

我们钦定左下角点为(1,1)，之后枚举右上角的点(i,j)，得到两个点之后答案就需要减去$(\gcd(i,j)-1) (n-i+1) (m-j+1)$.

#include <cstdio>
#define R register
int gcd(int a,int b) {return !b?a:gcd(b,a%b);}
int main()
{
	R int m,n;
	R long long ans;
	scanf("%d%d",&m,&n),m++,n++;
	ans=(1ll*m*n*(m*n-1)*(m*n-2)-1ll*n*(n-1)*(n-2)*m-1ll*m*(m-1)*(m-2)*n)/6;
	for(R int i=2;i<=m;++i)
		for(R int j=2;j<=n;++j)
			ans-=1ll*(gcd(i-1,j-1)-1)*(m-i+1)*(n-j+1)*2;
	printf("%lld\n",ans);
}