【模板】GCD & LCM

xxxasybt2023 · 2025-10-29 20:18:52 · 算法·理论

template <typename T>
inline T binary_gcd(T a,T b)
{
    int x = __builtin_ctz(a),y = __builtin_ctz(b),z = min(x,y),d;
    for (b >>= y;a;a >>= x,d = b-a,x = __builtin_ctz(d),(a<b) && (b=a),a = abs(d)) ;
    return b<<z;
}
template <typename T> inline T binary_lcm(T a,T b) {return a/binary_gcd(a,b)*b;}