Home > libalgo > 2進GCD

2進GCD

概要

以下を利用して，減算とシフト演算で GCD を計算する．

$\gcd(2a, 2b) = 2 \gcd(a, b)$
$\gcd(a, b) = \gcd(a - b, b)$, 奇数 - 奇数 = 偶数
$\gcd(2a, 2b + 1) = \gcd(a, 2b + 1)$

計算量

$O(\log(\min(a,b)))$

実装

template <typename Int>
Int binary_gcd(Int a, Int b) {
    if (a == 0 || b == 0) return a ? a : b;
    static const auto ctz = [](Int x) {
        int res = 0;
        for (; ~x & 1; x >>= 1, ++res)
            ;
        return res;
    };
    int s, t;
    a >>= (s = ctz(a));
    b >>= (t = ctz(b));
    while (a != b) {
        if (a > b) {
            a -= b;
            a >>= ctz(a);
        } else {
            b -= a;
            b >>= ctz(b);
        }
    }
    return a << (s < t ? s : t);
}