首页 > 题解 > bzoj 3505 [Cqoi2014]数三角形

bzoj 3505 [Cqoi2014]数三角形

Description

给定一个nxm的网格,请计算三点都在格点上的三角形共有多少个。下图为4x4的网格上的一个三角形。

注意三角形的三点不能共线。

Input

输入一行,包含两个空格分隔的正整数m和n。

Output

输出一个正整数,为所求三角形数量。

Sample Input

2 2

Sample Output

76

HINT

数据范围

1<=m,n<=1000

题解

随便选三个点C(N+1)(M+1),3,然后减去那些构成一条直线的。

有个定理(i,j)到(0,0)的连线上的整数点的个数是gcd(i,j)(包含(0,0)而不包含(i,j))。

我们在坐标系内作线段,首先斜率为负数的通过翻转肯定能变成斜率为正数的,所以只需统计斜率为正数的(斜率为0或不存在的可以单独算)。

一条斜率>0的线段肯定能够通过平移使得左下端点和(0,0)重合,因此我们就到结论上来了,只需统计每个点和(0,0)连线上有多少点,然后乘上(N+1-i)*(M+1-j),即通过平移找到多少条这样的线段。总数减去这些不合法线段个数就是答案。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×