【归档】花式求最大公因数

本博客源自我的洛谷博客https://www.luogu.com.cn/article/1jy3ro0r （现在改成专栏了），写作时间 2021-08-15 23:18

a 是 b 的约数 \iff a\,|\,b

x 是 a_1,a_2,...,a_i,...,a_n 的公约数 \iff
x 是 a_1,a_2,...,a_i,...,a_n 中所有数的约数

特别的：x 是 a，b 的公约数 \iff x\,|\,a\;\And x\,|\,b

一组整数的最大公约数，是指所有公约数里面最大的一个，记为 \gcd(...) 。

两个数的最大公约数

欧几里得算法

指路
，复杂度 O(\log n)

欧几里得优化 -> Stein算法

已知 a,b，求 \gcd(a,b)

先把 a,b 都变成奇数，记录 a,b 中含有多少公共的 2，最后乘回来。

类似欧几里得算法进行辗转相减/相除，此过程中得到的 a,b 可以放心的除以 2。

代码实现

1. 欧几里得 - 最朴素的递归

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

2. 欧几里得 - 不用递归

int gcd(int a,int b){
    if(b) while((a%=b)&&(b%=a));
    return a+b;
}

3. Stein算法 - 非位运算版

int gcd(int a,int b){ int c=0;
    if(a==0||b==0) return a+b;
    while(a%2==0&&b%2==0){a/=2;b/=2;c++;}
    while(a%2==0)a/=2; while(b%2==0)b/=2;
    if(a<b) swap(a,b);
    while(a%=b){while(a%2==0)a/=2;if(a<b)swap(a,b);} //此处括号中a%=b 可以换为 a=(a-b)/2，但亲测int下换了会变慢一点点
    return b<<c;
}

4. Stein算法 - 位运算版

int 下，改成位运算并不能使代码变快，反而使代码更长，可读性更差，不建议使用。

但倘若想求高精\gcd，且写了 2^k 压一位的高精模板的话，也许比非位运算版能快一些。

int gcd(int a,int b){int c=0;
	if(a==0)return b;if(b==0)return a;
	while((!(a&1))&&(!(b&1))){a>>=1;b>>=1;c++;}
	while((!(a&1)))a>>=1; while((!(b&1)))b>>=1;
	if(a<b)	swap(a,b);
	while(a=((a-b)>>1)){while((!(a&1)))a>>=1;if(a<b)swap(a,b);}//用高精的话换了快
	return b<<c;
}