前言

欧几里德算法又称辗转相除法是指用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

这是gcd的本职工作，代码也比较简单，证明就不再多解释。

Code

int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}

正文

接下来本文要讲的，才是gcd的正确打开方式。

OIer经常遇到这样的问题，就是如何判断在一个平面直角坐标系中或近似于平面直角坐标系中，判断两点之间有无其他整数点（横坐标和纵坐标都为整数的点），甚至让你求出具体个数。

比如这道例题。

EG

P1447 [NOI2010]能量采集

题目描述

栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后，栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。

栋栋的植物种得非常整齐，一共有n列，每列有m棵，植物的横竖间距都一样，因此对于每一棵植物，栋栋可以用一个坐标(x, y)来表示，其中x的范围是1至n，表示是在第x列，y的范围是1至m，表示是在第x列的第y棵。

由于能量汇集机器较大，不便移动，栋栋将它放在了一个角上，坐标正好是(0, 0)。

能量汇集机器在汇集的过程中有一定的能量损失。如果一棵植物与能量汇集机器连接而成的线段上有k棵植物，则能 量的损失为2k + 1。例如，当能量汇集机器收集坐标为(2, 4)的植物时，由于连接线段上存在一棵植物(1, 2)，会产生3的能量损失。注意，如果一棵植物与能量汇集机器连接的线段上没有植物，则能量损失为1。现在要计算总的能量损失。

下面给出了一个能量采集的例子，其中n = 5，m = 4，一共有20棵植物，在每棵植物上标明了能量汇集机器收集它的能量时产生的能量损失。

Solve

一般来说，大多数写题解的人，会直接告诉你这个奇怪的结论。

一个点（x,y）到原点之间的整数点个数即为gcd（x，y），包括（x,y)不包括原点，也就是k+1。

之前我试了试之后发现这竟然是对的，但是不知道为什么是对的。翻遍有关的题解和资料都没有详细的解释。于是秉着万丈高楼平地起，成功只能靠自己认真的原则，就自己探求了一下，终于探求到其中的一点奥秘，与大家分享下。

其实也不是多么高深的东西。

首先，将一个整数点（x，y）看作一个直角三角形或是一个矩形，边长为x和y。称他为三角形或矩形（x，y）。

然后，设gcd（x，y）=d，那么三角形（x/d，y/d）也是直角边为整数的三角形。

那么，x和y分别乘上d分之一，d分之二……直到d分之d。这其中所有的三角形的直角边边长都是整数，对应到平面直角坐标系上就是d个点，这一点可以性感感性理解一下，或想想三角形的相似，就可以明白了。

所以，一个点（x,y）到原点之间的整数点个数即为gcd（x，y），包括（x,y)不包括原点，也就是k+1。

这样再去分析类似的题目，就不会那么难搞了，也能看懂题解了。