整数の最大公約数（GCD）と最小公倍数（LCM）は数論の基礎概念であり、暗号アルゴリズムや最適化処理で頻繁に利用される。GCDは共通の約数の最大値、LCMは共通の倍数の最小値を指す。これらの値は a × b = GCD(a,b) × LCM(a,b) の関係で結ばれ、GCDを先に求めることでLCMを効率的に導出できる。

標準ライブラリを活用する方法（C++17以降）

C++17では<numeric>ヘッダに標準化された計算関数が提供される。符号付き整数に対応し、オーバーフロー対策が施されている。

#include <iostream>
#include <numeric>
#include <cmath>

int main() {
    const long x_val = 42;
    const long y_val = 105;
    
    const auto common_divisor = std::gcd(x_val, y_val);
    const auto common_multiple = std::lcm(x_val, y_val);
    
    std::cout << "入力値: " << x_val << " と " << y_val << "\n";
    std::cout << "GCD結果: " << common_divisor << "\n";
    std::cout << "LCM結果: " << common_multiple << "\n";
    
    return 0;
}

ユークリッドの互除法による実装

除算剰余を反復的に計算する手法で、計算量はO(log min(a,b))。数学的根拠はgcd(a,b) = gcd(b, a mod b)の等価性にある。負の値には絶対値を適用し、ゼロ値の場合は特別な処理が必要。

#include <iostream>
#include <cstdlib>

// 反復処理による実装
long compute_gcd(long m, long n) {
    m = std::abs(m);
    n = std::abs(n);
    
    while (n != 0) {
        const long remainder = m % n;
        m = n;
        n = remainder;
    }
    return m;
}

long compute_lcm(long p, long q) {
    if (p == 0 || q == 0) return 0;
    return std::abs(p / compute_gcd(p, q) * q);
}

int main() {
    const long num1 = 72;
    const long num2 = 120;
    
    std::cout << "GCD(" << num1 << ", " << num2 << ") = " 
              << compute_gcd(num1, num2) << "\n";
    std::cout << "LCM(" << num1 << ", " << num2 << ") = " 
              << compute_lcm(num1, num2) << "\n";
}

ビット演算を用いた高速化手法（Steinのアルゴリズム）

除算をビットシフトで置き換えることで効率化。2で割り切れる場合の特殊処理が特徴で、特に大きな数値の処理で優位性を発揮する。

long stein_gcd(long u, long v) {
    if (u == 0) return v;
    if (v == 0) return u;
    
    const int common_twos = __builtin_ctzll(u | v);
    u >>= __builtin_ctzll(u);
    
    do {
        v >>= __builtin_ctzll(v);
        if (u > v) {
            const long temp = u;
            u = v;
            v = temp;
        }
        v -= u;
    } while (v != 0);
    
    return u << common_twos;
}

このアルゴリズムは符号なし整数で定義されるが、絶対値を適用することで符号付き整数にも拡張可能。ハードウェアのビット操作命令を直接利用するため、特定の環境で性能が向上する。