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)所成线段，那么长度相同的线
题意 在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)所成线段，那么长度相同的线