competitive-programming-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub kmyk/competitive-programming-library

:heavy_check_mark: monoids/gcd.hpp

Depends on

Verified with

Code

#pragma once
#include "number/gcd.hpp"

/**
 * @note a semilattice
 */
template <class Integer>
struct gcd_monoid {
    typedef Integer value_type;
    Integer unit() const { return 0; }
    Integer mult(Integer a, Integer b) const { return gcd(a, b); }
};
#line 2 "number/gcd.hpp"
#include <algorithm>

/**
 * @note if arguments are negative, the result may be negative
 */
template <typename T>
T gcd(T a, T b) {
    while (a) {
        b %= a;
        std::swap(a, b);
    }
    return b;
}

template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}
#line 3 "monoids/gcd.hpp"

/**
 * @note a semilattice
 */
template <class Integer>
struct gcd_monoid {
    typedef Integer value_type;
    Integer unit() const { return 0; }
    Integer mult(Integer a, Integer b) const { return gcd(a, b); }
};
Back to top page