二进制gcd（binary gcd）小解

· · 算法·理论

前言：

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

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

由于机房电脑的原因，洛谷除了云剪贴板以外的 \LaTeX 都爆炸了，所以这篇文章一开始挂在了剪贴板上。

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

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

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

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

简介：

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

这项科技大大提高了最大公约数运算的效率——如果硬要说的话，就像是从 O(\log n) 到近似 O(1) 那么大吧。

……虽然这个东西的理论上界似乎还是 O(\log n) 来着。

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

原理：

对于 \gcd(a,b)，分为 5 种情况讨论：

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

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

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）
}

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

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

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 语句。

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

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：为了确保所讲的知识的时效性，“优异的表现”中的提交记录是在今天重新交的。）