This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub kmyk/competitive-programming-library
#include "monoids/gcd.hpp"
#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); }
};