tests/math/extgcd/ntl-1e.test.cpp

View this file on GitHub
Last update: 2025-03-03 00:33:48+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/cpp/library/6/NTL/1/NTL_1_E

Depends on

拡張ユークリッドの互除法 (extgcd) (library/math/extgcd.hpp)

Code

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using ull = unsigned long long;

#include "../../../cpp/library/math/extgcd.hpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/cpp/library/6/NTL/1/NTL_1_E"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int a, b;
  cin >> a >> b;
  auto res = asalib::math::extgcd<int>(a, b, gcd(a, b));
  assert(res);
  auto [x, y] = *res;
  cout << x << " " << y << endl;
  return 0;
}

#line 1 "tests/math/extgcd/ntl-1e.test.cpp"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using ull = unsigned long long;

#line 2 "library/math/extgcd.hpp"

#include <concepts>
#include <optional>
#line 6 "library/math/extgcd.hpp"
using namespace std;

namespace asalib {
  namespace math {
    // Returns a pair (x, y) such that ax + by = c
    template<integral T>
    constexpr optional<pair<T, T>> extgcd(T a, T b, T c) {
      if (b == 0) {
        if (c % a != 0) return nullopt;
        return make_pair(c / a, 0);
      }
      auto res = extgcd(b, a % b, c);
      if (!res) return nullopt;
      auto [x, y] = *res;
      return make_pair(y, x - (a / b) * y);
    }
  }  // namespace math
}  // namespace asalib
#line 8 "tests/math/extgcd/ntl-1e.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/cpp/library/6/NTL/1/NTL_1_E"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int a, b;
  cin >> a >> b;
  auto res = asalib::math::extgcd<int>(a, b, gcd(a, b));
  assert(res);
  auto [x, y] = *res;
  cout << x << " " << y << endl;
  return 0;
}