zrj2012-B3-0005

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题意很简单，给出一个N*M的矩形，求其中的三角形数。
如果我们直接算N*M个点中取3个的情况，其中不仅包含了所有三角形的数目，还包含了三点共线的情况。由于三点共线更直观，因此我们选择ans=c(n*m,3)-三点共线数，来计算。
显然，所有三点共线的情况包含：1、横着的；2、竖着的；3、斜着的。前两个很好算，第3个，其实就是有斜率的情况。我的算法是，计算一个矩形中，如果我定住其中2个点分别是左下角与右上角，第三个点在矩形内构成的三点共线数目，这样枚举所有矩形，然后在N*M的大矩形中进行平移、左右对称，就可以求出所有斜着的三点共线。这样算，必然不会又重复，而且能够包含所有斜着的三点共线。具体求法是，先枚举所有gcd(i,j)=1，以这样的(i,j)为基础斜率，然后构造(i*k,j*k)的矩阵，在这样的矩阵中，从左下到右上的三点共线方案数是（k-1）。
至于左上到右下，乘2就好了。

题意很简单，给出一个N*M的矩形，求其中的三角形数。

如果我们直接算N*M个点中取3个的情况，其中不仅包含了所有三角形的数目，还包含了三点共线的情况。由于三点共线更直观，因此我们选择ans=c(n*m,3)-三点共线数，来计算。

显然，所有三点共线的情况包含：1、横着的；2、竖着的；3、斜着的。前两个很好算，第3个，其实就是有斜率的情况。我的算法是，计算一个矩形中，如果我定住其中2个点分别是左下角与右上角，第三个点在矩形内构成的三点共线数目，这样枚举所有矩形，然后在N*M的大矩形中进行平移、左右对称，就可以求出所有斜着的三点共线。这样算，必然不会又重复，而且能够包含所有斜着的三点共线。具体求法是，先枚举所有gcd(i,j)=1，以这样的(i,j)为基础斜率，然后构造(i*k,j*k)的矩阵，在这样的矩阵中，从左下到右上的三点共线方案数是（k-1）。

至于左上到右下，乘2就好了。