关于最大公约数的求解,主要有欧几里得算法和Stein算法两种方法。
欧几里得算法
欧几里得算法的原理为:
若
$$a \equiv r(mod\ b)$$
则
$$gcd(a,b) = gcd(b,r)$$
算法执行过程为辗转相除法。
算法实现也很简单:
递归形式:
/**
* 求解 a, b 两个数的最大公约数。
*/
int gcd(int a, int b)
{
if(b == 0) {
return a;
}
return gcd(b, a%b);
}
非递归形式:
/**
* 求解 a, b 两个数的最大公约数。
*/
int gcd(int a, int b)
{
while(b > 0) {
int tmp = a % b;
a = b;
b = tmp;
}
return a;
}
欧几里得算法的时间复杂度为
,最坏情形为斐波那契数列的相邻两项。空间复杂度为
Stein算法
Stein算法是另一种求解两个数的最大公约数的算法。其原理为:
Stein算法的实现如下:
/**
* Stein算法
*
* 条件:0 <= b < a.
*/
int gcd(int a, int b)
{
int r = 0;
while(b > 0) {
if(a&0x01 == 0 && b&0x01 == 0) { // a, b 都为偶数
a >> 1; b >> 1; r = r + 1;
}
else if(a&0x01 == 0 && b&0x01 == 1) { // a 偶,b 奇
a >> 1;
}
else if() { // a 奇,b 偶
b >> 1;
}
else if() { // a 奇,b 奇
a = (a-b) >> 1;
}
if(a < b) {
a ^= b; b ^= a; a ^= b; // swap(a, b);
}
}
return a<<r;
}
与欧几里得算法相比,Stein 算法的优点在于不需要对大整数进行取模运算,只需要进行移位和减法运算。
扩展欧几里得算法
我也是刚刚弄懂,非递归的版本可以去看看资料,里面有
#include <stdio.h>
int x,y;
int egcd(int,int);
int main(void)
{
int a=7,b=5;
printf("%d",egcd(a,b));
return 0;
}
int egcd(int a,int b)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int r=egcd(b,a%b);
int t=x;
x=y;
y=t-a/b*y;
return r;
}
资料:
https://zh.wikipedia.org/wiki/%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95
http://www.nowamagic.net/academy/detail/40110168
http://www.nowamagic.net/academy/detail/40110119 这个不错