binary gcd
(src/math/binary_gcd.hpp)

• View this file on GitHub
• Last update: 2023-01-12 22:28:24+09:00
• Include: #include "src/math/binary_gcd.hpp"

概要

2 数の最大公約数を求める． 一般的な Euclid の互除法による実装と異なり，非再帰かつ除算が 2 で割るものしか登場しないので bit shift で済み，約 3 から 4 倍程度高速である．

補題

• $\gcd(0, x) = \gcd(x, x) = x$
• $\gcd(2x, 2y) = 2\gcd(x, y)$
• $\gcd(2x, y) = \gcd(x, y)$ if $y$ is odd
• $\gcd(x, y) = \gcd(x - y, y)$ if $x > y$

どれも理解及び証明は容易で，原理は実際にソースコードを見るのがわかりやすい． 特に $x, y$ が共に奇数ならば $x - y$ は偶数であるから効率的に計算することが可能である．

Verified with

• test/aoj/NTL_1_C.test.cpp

Code

#pragma once

template <typename T> T binary_gcd(T x_, T y_) {
    unsigned long long x = x_ < 0 ? -x_ : x_, y = y_ < 0 ? -y_ : y_;
    if (!x or !y) return x + y;
    int n = __builtin_ctzll(x), m = __builtin_ctzll(y);
    x >>= n, y >>= m;
    while (x != y) {
        if (x > y)
            x = (x - y) >> __builtin_ctzll(x - y);
        else
            y = (y - x) >> __builtin_ctzll(y - x);
    }
    return x << (n > m ? m : n);
}

#line 2 "src/math/binary_gcd.hpp"

template <typename T> T binary_gcd(T x_, T y_) {
    unsigned long long x = x_ < 0 ? -x_ : x_, y = y_ < 0 ? -y_ : y_;
    if (!x or !y) return x + y;
    int n = __builtin_ctzll(x), m = __builtin_ctzll(y);
    x >>= n, y >>= m;
    while (x != y) {
        if (x > y)
            x = (x - y) >> __builtin_ctzll(x - y);
        else
            y = (y - x) >> __builtin_ctzll(y - x);
    }
    return x << (n > m ? m : n);
}

Back to top page