算法杂项

数论部分

两个数互质则不能由 p, q 凑出来的最大的数为 (p - 1) * (q - 1) - 1;

平面直角坐标系部分

皮克定理：

定理： 皮克定理是指一个计算点阵中顶点在格点上的多边形面积公式，该公式可以表示为 S = a + b/2 - 1，其中 a 表示多边形内部的点数，b 表示多边形落在格点边界上的点数，S 表示多边形的面积。

结论： s(面积) = a(中间的点) + b(边上的点) / 2 - 1

两点(x1, y1)(x2, y2)的连线上的整点数 ：

结论： abs(gcd(x1 - x2, y1 - y2))

证明

• 将该直线其中一点移动到原点(0, 0)，另一点为(a, b)，则该直线斜率为 b’ / a’ (约分过)，则该支线上的所有点一定为 k * (b' / a')，k 可取 1, 2, 3, …… , gcd(a, b)。化为原坐标即为 gcd(x1 - x2, y1 - y2) , 因为 gcd 函数可能得负数，所以取 绝对值 abs()