alg/monoid/lcm.hpp

• View this file on GitHub
• Last update: 2023-07-03 05:47:01+09:00
• Include: #include "alg/monoid/lcm.hpp"

Code

// 大きいときは infty<T>
template <typename T>
struct Monoid_Lcm {
  using value_type = T;
  using X = value_type;
  static X op(X x, X y) {
    if (x == infty<T> || y == infty<T>) return infty<T>;
    x /= gcd(x, y);
    if (x >= ceil(infty<T>, y)) return infty<T>;
    return x * y;
  }
  static constexpr X unit() { return 1; }
  static constexpr bool commute = 1;
};

#line 1 "alg/monoid/lcm.hpp"

// 大きいときは infty<T>
template <typename T>
struct Monoid_Lcm {
  using value_type = T;
  using X = value_type;
  static X op(X x, X y) {
    if (x == infty<T> || y == infty<T>) return infty<T>;
    x /= gcd(x, y);
    if (x >= ceil(infty<T>, y)) return infty<T>;
    return x * y;
  }
  static constexpr X unit() { return 1; }
  static constexpr bool commute = 1;
};

Back to top page