二进制gcd（binary gcd）小解

前言：

很久以前给机房同学讲初等数论的时候写的东西。

（当时问他们要不要听科技，结果得到了相当一致的“不要”的回答。）

由于机房电脑的原因，洛谷除了云剪贴板以外的

\LaTeX

都爆炸了，所以这篇文章一开始挂在了剪贴板上。

后来在清理剪贴板的时候发现了这一篇，于是就重新上传了文章。

可能有些用语比较奇怪，不要在意。

对于文章中没有讲清楚的一些细节（虽然我自认为讲得还算比较清晰），可以去网上自行搜索相关博客学习。

（话说我当时是照着哪一篇博客学的来着？……不管了，忘了就忘了吧。）

简介：

二进制 gcd（binary gcd）是一种适宜在需要卡常的情景下使用的科技。

这项科技大大提高了最大公约数运算的效率——如果硬要说的话，就像是从

O(\log n)

到近似

O(1)

那么大吧。

……虽然这个东西的理论上界似乎还是

O(\log n)

来着。

不过，二进制 gcd 实际上很难卡到上界——或者说，就算特意去卡的话，也比一般的 gcd 跑的要快很多。

原理：

对于

\gcd(a,b)

，分为

5

种情况讨论：

$a=b$ 。此时显然有 $\gcd(a,b)=a=b$ ，直接返回 $a$ 或 $b$ 即可。
$a=0$ 或 $b=0$ 。此时直接返回不为零的数即可（如果两个数都为 $0$ ，则转到情况 $1$ ）。
$2\mid a$ 且 $2\mid b$ 。此时 $2$ 显然是 $a$ 与 $b$ 的公约数，那么有 $\gcd(a,b)=2\cdot\gcd(\frac{a}{2},\frac{b}{2})$ 。
$2\mid a$ 或 $2\mid b$ 。此时 $2$ 一定不是 $a$ 与 $b$ 的公约数，那么有 $\gcd(a,b)=\gcd(\frac{a}{2},b)$ （设此时 $2\mid a$ ）。
$2\nmid a$ 且 $2\nmid b$ 。此时采用更相减损术，则有 $\gcd(a,b)=\gcd(b,a-b)$ （设此时 $a>b$ ）；

由于 $a$ 与 $b$ 均为奇数，则 $a-b$ 一定为偶数，于是转到情况 $4$ ，那么有 $\gcd(a,b)=\gcd(b,a-b)=\gcd(a,\frac{a-b}{2})$ 。

根据上述原理，我们可以写出代码：

CPP

ll gcd(ll a,ll b)
{
	if(a==b)return a;//如果 a=b（情况 1）
	if(!a)return b;//如果 a=0（情况 2）
	if(!b)return a;//如果 b=0（情况 2）
	if(~a&1)//如果 a 是偶数
	{
		if(b&1)return gcd(a>>1,b);//如果 b 是奇数（情况 4）
		else return gcd(a>>1,b>>1)<<1;//如果 b 是偶数（情况 3）
	}
	if(~b&1)return gcd(a,b>>1);//如果 a 是奇数且 b 是偶数（情况 4）
	return a>b?gcd(b,a-b>>1):gcd(a,b-a>>1);//其余的情况，即 a 与 b 都是奇数（情况 5）
}

随后我们发现：虽然位运算为我们优化了大量的常数，但基于递归的实现方式使得该算法的效率仍然较低。

那么，在将递归改为循环后，我们可以得到这一版代码：

CPP

ll gcd(ll a,ll b)
{
	if(a==b)return a;//如果 a=b（情况 1）
	if(!a)return b;//如果 a=0（情况 2）
	if(!b)return a;//如果 b=0（情况 2）
	ll z=0;//z 表示 a 与 b 末尾的 0 的个数的最小值，用于处理情况 3（即提出 a 与 b 中所有的公因数 2）
	while(~(a|b)&1){a=a>>1;b=b>>1;++z;}//提取出 a 与 b 中作为公因数存在的 z 个 2
	//提取完成后，a 与 b 一定有至少一个是奇数，转入情况 4 或情况 5
	while(~(a&1))a=a>>1;//为方便处理，令 a 一定为奇数
	do
	{
		while(~(b&1))b=b>>1;//根据情况 4，b 中的质因子 2 不影响最终答案，可以直接除掉，除掉后转入情况 5
		if(a>b)swap(a,b);b=b-a;//根据情况 5，执行更相减损术
	}
	while(b);//更相减损术终止条件：减数与差相等，即再执行一次更相减损术后，差会变为 0
	return a<<z;//根据情况 3，将共有的公因数（z 个 2）乘回去
}

然而，我们在提取

a

与

b

的末尾的

0

的个数时使用了大量的 while 语句，这使得我们的常数比之前的代码还要高一个数量级。

那么，有没有方法能够做到

O(1)

实现上述操作呢？

答案是有的。利用硬件函数 __builtin_ctz()（于 C++14 起便可以使用），我们可以继续加速算法。

同时，可以注意到：只有在直接输入

0

的时候，才可能出现

a=0

或者

b=0

的情况。因此，在能够保证输入不为

0

的时候，可以直接删去后两个 if 语句。

根据以上论述，外加一些卡常技巧，我们可以得出最终代码（原理与上一版大致相同，故不添加注释）：

CPP

ll gcd(ll a,ll b)
{
	if(a==b)return a;
	ll az=__builtin_ctzll(a),bz=__builtin_ctzll(b),z=az<bz?az:bz,f;
	a=a>>az;
	while(b)
	{
		b=b>>bz;f=b-a;
		bz=__builtin_ctzll(f);
		a=b<a?b:a;b=f<0?-f:f;
	}
	return a<<z;
}

经过实际测试，这一版代码在需要对

\gcd(a,b)

进行

O(\text{值域})

预处理，

O(1)

查询的 P5435 基于值域预处理的快速 GCD 中取得了优异的表现。

（2025.8.15 upd：为了确保所讲的知识的时效性，“优异的表现”中的提交记录是在今天重新交的。）

二进制gcd（binary gcd）小解

文章操作

前言：

简介：

原理：

相关推荐

评论

二进制gcd（binary gcd）小解