Binary GCD 学习笔记

算是一点杂项吧，感觉没什么机会用上。

0x00 前言

有时你需要大量且快速的求 gcd ，像P5435。但是对值域预处理 gcd 又很麻烦，所以这时候我们可以考虑 Binary GCD 。

0x01 原理

Binary GCD 的时间复杂度是 \(\Theta(\log n)\) 的，和欧几里得算法（即“辗转相除法”）相同。但是在实战中，由于 Binary GCD 的实现大量依靠位运算，因此速度非常快，在极端情况下远优于欧几里得算法。

0x02 方法

假设现在我们需要求 \(\gcd(a,b)\) ，那么可以分成以下 5 种情况：

第一种， \(a=b\) 。显然 \(\gcd(a,b)=a\) ；

第二种， \(a=0\) 或 \(b=0\) 。当 \(b=0\) 时 \(\gcd(a,b)=a\) ， \(a=0\) 时 \(\gcd(a,b)=b\) ；

第三种， \(a,b\equiv0\pmod2\) 。对于这种情况，显然 2 是公约数之一，直接得到 \(\gcd(a,b)=\gcd(\frac{a}{2},\frac{b}{2})\) ；

第四种， \(a\equiv0\pmod2\) 或 \(b\equiv0\pmod2\)。不妨设 \(a\equiv0\pmod2\) ，那么显然 2 不是公约数之一，直接得到 \(\gcd(a,b)=\gcd(\frac{a}{2},b)\) ；

第五种， \(a,b\equiv1\pmod2\) 。不妨设 a>b ，根据“更相减损术”有 \(\gcd(a,b)=\gcd(a−b,b)\) ，此时就变成了第四种情况，即 \(\gcd(a,b)=\gcd(\frac{a-b}{2},b)\) 。

0x03 实现

根据上文，我们可以写出这样的原始代码：

int gcd(int a,int b){
	if(a==b)return a;
	if(!a)return b;
	if(!b)return a;
	if(~a&1){
		if(b&1)return gcd(a>>1,b);
		else return gcd(a>>1,b>>1)<<1;
	}
	if(~b&1)return gcd(a,b>>1);
	if(a>b)return gcd((a-b)>>1,b);
	return gcd((b-a)>>1,a);
}

0x03.5 优化

当然，这样还是需要大量的递归与判断，所以我们有优化版：

int gcd(int a,int b){
	int az=__builtin_ctz(a);
	int bz=__builtin_ctz(b);
	int z=min(az,bz);b>>=bz;
	while(a){
		a>>=az;int diff=a-b;
		az=__builtin_ctz(diff),b=min(a,b),a=abs(diff);
	}
	return b<<z;
} 

其中 \(\text{__builtin_ctz(x)}\) 函数会返回 \(x\) 的二进制下末尾的 0 的个数。

0x04 总结

我也不知道这有啥用。在遇到需要大量且快速的求 gcd 的情况时， Binary GCD 可以帮你略过繁琐的预处理。