无

知识点wiki。

知识点wiki。

CQOI2014 数三角形

给定一个$N\times M$的网格，请计算三点都在格点上的三角形共有多少个。

题解：容斥原理。$C_{(N+1)(M+1)}^3$减去三点共线的三角形。

对于三点共线的三角形，可以枚举比较长的那条边的横向长度和纵向长度$x,y$，这条线段之间有$gcd(x,y)+1$个整点。这样的线段有$2(n-x+1)(m-y+1)$条。

还需判断一下两点重合和三点重合的三角形。