team2012-B2-sol-0005

从 Trac 迁移的文章

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

原文章内容如下：

题意：求出M*N的格点图中的三角形数量（不包括三点共线）
思路：三点共线的情况相对好求些。ANS = C(m*n,3) - 三点共线数量
求三点共线数量：对于一个矩形x*y，其中两个点在1条对角线上的三点共线有gcd(x,y)-1个，矩形有两条对角线，需要*2，枚举所有矩形的大小（此时个数可以O(1)计算）即可。

题意：求出M*N的格点图中的三角形数量（不包括三点共线）

思路：三点共线的情况相对好求些。ANS = C(m*n,3) - 三点共线数量

求三点共线数量：对于一个矩形x*y，其中两个点在1条对角线上的三点共线有gcd(x,y)-1个，矩形有两条对角线，需要*2，枚举所有矩形的大小（此时个数可以O(1)计算）即可。