将一个长为m宽为n的矩形划分成 m * n 个单元格作一条对角线标记该对角线与单元格的交点,有如下结论单条对角线经过的单元格数量为 m n - gcd(m,n)从 (0,0) 到 (m,n) 的直线在单位格中经过的格点包括端点数量是 gcd(m,n) 1如果只算内部格点就是 gcd(m,n) - 1单条对角线的交点数|S1| m n 1 - gcd(m,n) 两条对角线共同的交点数:2*(a b - gcd(a,b) - 1) - (a%20 || b%20 ? 1 : 0)。1.单条对角线经过的单元格数量为mn-gcd(m,n)1若m和n互为质数即gcd(m,n)1此时对角线与矩形只有两个端点在格点上内部没有位于格点的交点。ps:当横向交点与纵向交点重合时重复计算交点需减去。可知横向有m1个交点蓝色紫色纵向有n1个交点粉色紫色两个端点各被水平和竖直边界重复计算一次紫色所以要减去2共有(m1)(n1)-2mn个交点mn个交点将对角线分成mn-1段每段经过1个单元格共经过mn-1个单元格。2当m和n不互质时令d为二者的最大公约数即gcd(m,n)d, 此时m/d和n/d互质。取长m/d、宽n/d的小矩形此时由1可知对角线经过m/dn/d-1个单元格,大矩形共经过d*(m/dn/d-1)mn-gcd(m,n)个单元格。2.从 (0,0) 到 (m,n) 的直线经过的格点包括端点数量是 gcd(m,n) 1内部格点数是 gcd(m,n) - 1令gcd(m,n) dmn), 则m是n的d倍x 和 y n * x (0xd,x取整) 均为整数此时x,y)在格点上。因此包括端点的格点数为gcd(m,n) 1,内部格点数为gcd(m,n)-1。3.单条对角线的交点数|S1| m n 1 - gcd(m,n)|S1| 垂直线数 水平线数 - 顶点数。由2可知|S1| (m 1) (n 1) - (gcd(m,n) 1) m n 1 - gcd(m,n)。4.两条对角线共同的交点数:2*(a b - gcd(a,b) - 1) - (a%20 || b%20 ? 1 : 0)两条对角线唯一的交点是矩形墙壁的中心点。只有当这个中心点恰好落在某条网格线上时它才会被我们计入 |S1| 和 |S2|。墙壁的中心点坐标可以表示为 (m/2,n/2)。每条对角线内部交点数为 m n - gcd(m,n) - 1两条合计2*(m n - gcd(m,n) - 1)如果 m 和 n 有一个是偶数中心点就会落在网格线上并被重复计算所以要减 1。因此答案 2*(m n - gcd(m,n) - 1) - (m%20 || n%20 ? 1 : 0)。练习墙壁划线容斥原理
