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

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

《挑战程序设计竞赛》2.6节第一道题中讲解了求线段上格点个数的问题,该解答给出了结果,但中间过程省略了不少内容。本文补充了相关的证明和解释。
问题描述如下:
格点是指平面坐标系中,横纵坐标都是整数的点。给定平面上两个格点,P1(x1,y1),P2(x2,y2),则线段P1P2上除了P1和P2外,有几个格点?事实上,该问题答案为|x2-x1|和|y2-y1|的最大公约数减1,并给出了一个图示。本文对该结论给出了证明。