辗转相除法（求最大公约数）

辗转相除法（求最大公约数）

做算法题，总是会遇到求两个数的最大公约数的场景，但是一直不记得这个算法，或者这个算法记得不熟。今天来记录一下。

引入

149. 直线上最多的点数

这道题目中，要求我们找到图中所有的点，最多点的一条直线的点数是多少。我们就需要用到求x和y最大公约数来对斜率进行标准化，也可以说是归一化。

原理

辗转相除法的过程如下例子。

例子：求 GCD(48, 18)

我们按照规则来：

gcd(48, 18)
= gcd(18, 48 % 18)   // 48 ÷ 18 = 2 余 12
= gcd(18, 12)
= gcd(12, 6)
= gcd(6, 0)          // 到 0 了，返回 6

答案是 6。

gcd(a,b) = gcd(b,a%b)，直到b等于0的时候返回a。

核心思想其实就是如果一个数能整除a和b，那么它一定可以被a-b整除，也一定能被a-nb整除（nb<=a）。所以我们每次将a和b缩小为b，a%b。a%b的操作其实就相当于约掉了b还剩下的数，该数也要能被最大公约数约掉。

总结

“用大除小取余数，小与余数变成新的一对，直到余数为 0”