Test/Math/EuclideanAlgorithm_gcd.test.cpp

• View this file on GitHub
• Last update: 2025-07-06 21:41:14+09:00
• Problem: https://yukicoder.me/problems/no/415

Depends on

• Library/Math/EuclideanAlgorithm.hpp
• Library/Utility/Tuple.hpp
• Library/Utility/io.hpp

Code

#define PROBLEM "https://yukicoder.me/problems/no/415"

// begin:tag includes
#include "../../Library/Math/EuclideanAlgorithm.hpp"
#include "../../Library/Utility/io.hpp"
// end:tag includes

#include <iostream>

signed main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);

  auto [n, d] = mtd::io::in<int, int>();
  auto ea = mtd::EuclideanAlgorithm(n, d);
  std::cout << n / ea.gcd() - 1 << std::endl;
}

#line 1 "Test/Math/EuclideanAlgorithm_gcd.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/415"

// begin:tag includes
#line 2 "Library/Math/EuclideanAlgorithm.hpp"

#include <iostream>

#include <numeric>

#include <tuple>


namespace mtd {

  class EuclideanAlgorithm {
    using T = long long;

    // 大きすぎるとオーバーフローしてしまう

    const static inline T m_mx = 1e9;

    const T m_a;
    const T m_b;
    const T m_c;

    T m_gcd;
    T m_x;
    T m_y;

    auto excludedEuclidAlgorithm(T a, T b) -> std::tuple<T, T, T> {
      if (a < 0) {
        auto [g, x, y] = excludedEuclidAlgorithm(-a, -b);
        return {g, -x, -y};
      }
      if (b == 0) { return {a, 1, 0}; }
      auto [g, y, x] = excludedEuclidAlgorithm(b, a % b);
      y -= a / b * x;
      return {g, x, y};
    }

    auto kRange(T x, T b, T l) const -> std::pair<T, T> {
      // x + b * k >= l を満たす k の範囲を求める

      T xd = (l - x);
      if (b == 0 && x >= l) { return {-m_mx, m_mx}; }
      if (b == 0 && x < l) { return {m_mx, -m_mx}; }
      if (b > 0 && xd < 0) { return {xd / b, m_mx}; }
      if (b > 0 && xd >= 0) { return {(xd + b - 1) / b, m_mx}; }
      if (b < 0 && xd < 0) { return {-m_mx, (-xd) / (-b)}; }
      if (b < 0 && xd >= 0) { return {-m_mx, -(xd - b - 1) / (-b)}; }
      return {m_mx, -m_mx};
    }

  public:
    auto debug() const {
      std::cout << m_a << " * " << m_x << " + " << m_b << " * " << m_y << " = "
                << m_c << std::endl;
      std::cout << "calc: " << m_a * m_x + m_b * m_y << " = " << m_c
                << std::endl;
    }

    EuclideanAlgorithm(T a, T b, T c) : m_a(a), m_b(b), m_c(c) {
      if (a == 0 && b == 0) { throw std::runtime_error(""); }
      auto [g, x, y] = excludedEuclidAlgorithm(a, b);
      if (c % g > 0) {
        throw std::runtime_error(
            "There is no solution to the equation. c must be divisible by "
            "gcd(a,b).");
      }
      m_gcd = g;
      m_x = c / g * x;
      m_y = c / g * y;
    }
    EuclideanAlgorithm(T a, T b) : EuclideanAlgorithm(a, b, std::gcd(a, b)) {}

    auto gcd() const { return m_gcd; }
    auto get(T x, T y) const { return m_a * x + m_b * y; }
    auto get(T k) const -> std::pair<T, T> {
      if (m_b == 0) { return {m_x, m_y - k}; }
      if (m_a == 0) { return {m_x + k, m_y}; }
      return {m_x + m_b * k, m_y - m_a * k};
    }
    // x>=x_lとなるようなkの範囲

    auto getMinX(T x_l = 0) const -> std::pair<T, T> {
      return kRange(m_x, m_b, x_l);
    }
    // y>=y_lとなるようなkの範囲

    auto getMinY(T y_l = 0) const -> std::pair<T, T> {
      return kRange(m_y, -1 * m_a, y_l);
    }
    // x>=x_l, y>=y_lとなるようなkの範囲

    auto getMin(T x_l = 0, T y_l = 0) const -> std::pair<T, T> {
      auto [xl, xr] = getMinX(x_l);
      auto [yl, yr] = getMinY(y_l);
      return {std::max(xl, yl), std::min(xr, yr)};
    }
  };

}  // namespace mtd

#line 2 "Library/Utility/io.hpp"

#line 4 "Library/Utility/io.hpp"
#include <ranges>
#include <type_traits>
#include <vector>

#line 2 "Library/Utility/Tuple.hpp"

#include <functional>

namespace mtd {
  namespace util {
    template <class F, class T>
    constexpr auto tuple_transform(F&& f, T&& t) {
      return std::apply(
          [&]<class... Ts>(Ts&&... elems) {
            return std::tuple<std::invoke_result_t<F&, Ts>...>(
                std::invoke(f, std::forward<Ts>(elems))...);
          },
          std::forward<T>(t));
    }
    template <class F, class T>
    constexpr auto tuple_for_each(F&& f, T&& t) {
      std::apply(
          [&]<class... Ts>(Ts&&... elems) {
            (std::invoke(f, std::forward<Ts>(elems)), ...);
          },
          std::forward<T>(t));
    }
  }  // namespace util
}  // namespace mtd
#line 9 "Library/Utility/io.hpp"

namespace mtd {
  namespace io {

    namespace __details {
      template <typename T>
      concept is_vec = std::same_as<
          T, std::vector<typename T::value_type, typename T::allocator_type>>;
      template <typename T>
      concept is_mat = is_vec<T> && is_vec<typename T::value_type>;

    }  // namespace __details

    template <class T>
    constexpr auto _input() {
      T x;
      std::cin >> x;
      return x;
    }
    template <typename T>
    requires requires { typename std::tuple_size<T>::type; }
    constexpr auto _input() {
      T x;
      util::tuple_for_each([](auto&& i) { std::cin >> i; }, x);
      return x;
    }
    template <__details::is_vec T>
    constexpr auto _input(int n) {
      std::vector<typename T::value_type> v;
      v.reserve(n);
      for (auto i : std::views::iota(0, n)) {
        v.emplace_back(_input<typename T::value_type>());
      }
      return v;
    }
    template <__details::is_mat T>
    constexpr auto _input(int h, int w) {
      T mat;
      mat.reserve(h);
      for (auto i : std::views::iota(0, h)) {
        mat.emplace_back(_input<typename T::value_type>(w));
      }
      return mat;
    }

    template <int N, class Tuple, class T, class... Args, class... Sizes>
    constexpr auto _tuple_input(Tuple& t, Sizes... sizes);
    template <int N, class Tuple, __details::is_vec T, class... Args,
              class Size, class... Sizes>
    constexpr auto _tuple_input(Tuple& t, Size size, Sizes... sizes);
    template <int N, class Tuple, __details::is_mat T, class... Args,
              class Size, class... Sizes>
    constexpr auto _tuple_input(Tuple& t, Size size_h, Size size_w,
                                Sizes... sizes);

    template <int N, class Tuple, class T, class... Args, class... Sizes>
    constexpr auto _tuple_input(Tuple& t, Sizes... sizes) {
      std::get<N>(t) = _input<T>();
      if constexpr (sizeof...(Args) > 0) {
        _tuple_input<N + 1, Tuple, Args...>(t, sizes...);
      }
    }
    template <int N, class Tuple, __details::is_vec T, class... Args,
              class Size, class... Sizes>
    constexpr auto _tuple_input(Tuple& t, Size size, Sizes... sizes) {
      std::get<N>(t) = _input<T>(size);
      if constexpr (sizeof...(Args) > 0) {
        _tuple_input<N + 1, Tuple, Args...>(t, sizes...);
      }
    }
    template <int N, class Tuple, __details::is_mat T, class... Args,
              class Size, class... Sizes>
    constexpr auto _tuple_input(Tuple& t, Size size_h, Size size_w,
                                Sizes... sizes) {
      std::get<N>(t) = _input<T>(size_h, size_w);
      if constexpr (sizeof...(Args) > 0) {
        _tuple_input<N + 1, Tuple, Args...>(t, sizes...);
      }
    }

    template <class... Args, class... Sizes>
    requires(std::convertible_to<Sizes, size_t>&&...) constexpr auto in(
        Sizes... sizes) {
      auto base = std::tuple<Args...>();
      _tuple_input<0, decltype(base), Args...>(base, sizes...);
      return base;
    }

  }  // namespace io

}  // namespace mtd
#line 6 "Test/Math/EuclideanAlgorithm_gcd.test.cpp"
// end:tag includes

#line 9 "Test/Math/EuclideanAlgorithm_gcd.test.cpp"

signed main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);

  auto [n, d] = mtd::io::in<int, int>();
  auto ea = mtd::EuclideanAlgorithm(n, d);
  std::cout << n / ea.gcd() - 1 << std::endl;
}

Back to top page