結果

問題 No.415 ぴょん
ユーザー cutmdocutmdo
提出日時 2024-08-30 15:43:53
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 4,128 bytes
コンパイル時間 1,703 ms
コンパイル使用メモリ 110,236 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-08-30 15:43:56
合計ジャッジ時間 2,625 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 2 ms
6,944 KB
testcase_16 AC 2 ms
6,944 KB
testcase_17 AC 2 ms
6,940 KB
testcase_18 AC 2 ms
6,940 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 AC 2 ms
6,940 KB
testcase_21 AC 2 ms
6,940 KB
testcase_22 AC 2 ms
6,944 KB
testcase_23 AC 2 ms
6,944 KB
testcase_24 AC 2 ms
6,944 KB
testcase_25 AC 2 ms
6,940 KB
testcase_26 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#include <iostream>
#include <numeric>
#include <tuple>
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> {        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};  }  auto getMinX(T x_l = 0) const -> std::pair<T, T> {    return kRange(m_x, m_b, x_l);  }  auto getMinY(T y_l = 0) const -> std::pair<T, T> {    return kRange(m_y, -1 * m_a, y_l);  }  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)};  }};
#include <iostream>
#include <ranges>
#include <type_traits>
#include <vector>
namespace mtd {  namespace io {    namespace type {      template <class T, int Pre = 1, int Size = 0>      struct vec {        using value_type = T;        static constexpr int pre = Pre;        static constexpr int size = Size;      };      template <class T>      concept is_vec = requires {        std::is_same_v<T, vec<typename T::value_type, T::pre, T::size>>;      };    }      template <type::is_vec T>    auto _input(int n) {      std::vector<typename T::value_type> v(n);      for (auto i : std::views::iota(0, n)) { std::cin >> v[i]; }      return v;    }    template <class T>    auto _input() {      T x;      std::cin >> x;      return x;    }    template <int N, class Tuple, class T, class... Args>    auto _tuple_input(Tuple& t) {      if constexpr (type::is_vec<T>) {        if constexpr (T::size == 0) {          std::get<N>(t) = _input<T>(std::get<N - T::pre>(t));        } else {          std::get<N>(t) = _input<T>(T::size);        }      } else {        std::get<N>(t) = _input<T>();      }      if constexpr (sizeof...(Args) > 0) {        _tuple_input<N + 1, Tuple, Args...>(t);      }    }    template <class T>    struct _Converter {      using type = T;    };    template <class T, int Pre, int Size>    struct _Converter<type::vec<T, Pre, Size>> {      using type = std::vector<T>;    };    template <class... Args>    auto in() {      auto base = std::tuple<typename _Converter<Args>::type...>();      _tuple_input<0, decltype(base), Args...>(base);      return base;    }  }  }  

#include <iostream>

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

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