最大公约数算法

• 师从
• 辗转相除法（欧几里得算法）
• 时间复杂度
• 更相减损术（《九章算术》）
• 时间复杂度
• 二分化更相减损术
• 思路
• 优化
• 时间复杂度

师从

本篇是观Vita君算法视频后总结，他是bilibili一位小up主：小学生Vita君
正所谓“生乎吾后，其闻道也亦先乎吾，吾从而师之”，诚然如此。

辗转相除法（欧几里得算法）

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

时间复杂度

O(logn)

更相减损术（《九章算术》）

int gcd2(int a, int b)
{
	if (a == b) return a;
	return (a > b) ? gcd2(a - b, b) : gcd2(a, b - a);
}

时间复杂度

O(n)

二分化更相减损术

int gcd3(int a, int b)
{
	if (a == b) return a;
	if (a & 1) {
		if (b & 1) return (a > b) ? gcd3(a - b, b) : gcd3(b - a, a);//4）
		return gcd3(a, b >> 1);//3）
	}
	if (b & 1) return gcd3(a >> 1, b);//2）
	return gcd3(a >> 1, b >> 1) << 1;//1）
}

思路

① a为偶数，b为偶数，gcd(a,b)=gcd(a/2,b/2)*2；
② a为偶数，b为奇数，gcd(a,b)=gcd(a/2,b)；
③ a为奇数，b为偶数，gcd(a,b)=gcd(a,b/2)；
④ a为奇数，b为奇数，a>b时，gcd(a,b)=gcd(a-b,b)， a<b时，gcd(a,b)=gcd(a,b-a)

优化

1）规避了性能较差的模运算；
2）改善了更相减损术的效率；
3）其中的位运算分别对速度优化
/////a & 1，将a的二进制数与1进行与运算，实现a % 2；
/////a >> 1，将a的二进制数右移一位，实现a / 2；
/////a << 1，将a的二进制数左移一位，实现a * 2；

时间复杂度

O(logn)