《挑战程序设计竞赛》读书笔记（四）格点问题的证明

《挑战程序设计竞赛》2.6节第一道题中讲解了求线段上格点个数的问题，该解答给出了结果，但中间过程省略了不少内容。本文补充了相关的证明和解释。

问题描述如下：

格点是指平面坐标系中，横纵坐标都是整数的点。给定平面上两个格点，P1(x1,y1)，P2(x2,y2)，则线段P1P2上除了P1和P2外，有几个格点？

例如：P1=(1,11)，P2=(5,3)，则格点有(2,9), (3,7), (4,5)三个。

一种朴素的想法是枚举满足 min(x1,x2)<= x <= max(x1,x2), min(y1,y2)<= y <= max(y1,y2)的所有x,y，判断是否在线段上，其复杂度为O(|x2-x1|*|y2-y1|)。

书中说，事实上，该问题答案为|x2-x1|和|y2-y1|的最大公约数减1，并给出了一个图示如图。

图中画的最下面的一个三角形正好以P2结尾，说明该问题答案为|x2-x1|和|y2-y1|的最大公约数减1。书中并未给出这个证明。本文将说明，最下面的一个三角形确实是正好以P2结尾。我们用反证法来证明。假设最下面的一个三角形不是正好以P2结尾，则可能是如下的情况，如图2。

如图，假设A1,…An是P1P2上的所有格点，且A1是离P1最近的格点。如果最后一个三角形AnCnP3不是正好以P2结束，则我们可以将三角形AnBnP2平移至三角形P1B1A1中，如图3。则E1也是格点，与A1是离P1最近的格点矛盾。得证。

得到了这个结论，剩下的就可以用辗转相除法求得最终的结果。

2.6节其他题目涉及到数论。没学过数论真是硬伤啊，等以后补充了相关知识之后再补充本章节其他内容。