library/algebra/monoid/Gcd.hpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Include: #include "library/algebra/monoid/Gcd.hpp"

Depends on

build/pch/stdc++.hpp

Verified with

test/yukicoder/1036.test.cpp

Code

template <typename X> struct MonoidGcd {
    using value_type = X;
    static constexpr X op(const X &x, const X &y) noexcept {
        return std::gcd(x, y);
    }
    static constexpr void Rchop(X &x, const X &y) { x = std::gcd(x, y); }
    static constexpr void Lchop(const X &x, X &y) { y = std::gcd(x, y); }
    static constexpr X unit() { return 0; }
    static constexpr bool commute = true;
};

#line 1 "library/algebra/monoid/Gcd.hpp"
template <typename X> struct MonoidGcd {
    using value_type = X;
    static constexpr X op(const X &x, const X &y) noexcept {
        return std::gcd(x, y);
    }
    static constexpr void Rchop(X &x, const X &y) { x = std::gcd(x, y); }
    static constexpr void Lchop(const X &x, X &y) { y = std::gcd(x, y); }
    static constexpr X unit() { return 0; }
    static constexpr bool commute = true;
};