tests/extgcd.test.cpp

• View this file on GitHub
• Last update: 2025-01-22 03:51:11+00:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_E

Depends on

• std::abs(x) extended for my library (tools/abs.hpp)
• Extended Euclidean algorithm (tools/extgcd.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_E

#include <iostream>
#include "tools/extgcd.hpp"

using ll = long long;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  ll a, b;
  std::cin >> a >> b;

  const auto [x0, y0, gcd] = tools::extgcd(a, b);
  std::cout << x0 << ' ' << y0 << '\n';

  return 0;
}

#line 1 "tests/extgcd.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_E

#include <iostream>
#line 1 "tools/extgcd.hpp"



#include <tuple>
#include <utility>
#include <cassert>
#include <algorithm>
#line 1 "tools/abs.hpp"



namespace tools {
  constexpr float abs(const float x) {
    return x < 0 ? -x : x;
  }
  constexpr double abs(const double x) {
    return x < 0 ? -x : x;
  }
  constexpr long double abs(const long double x) {
    return x < 0 ? -x : x;
  }
  constexpr int abs(const int x) {
    return x < 0 ? -x : x;
  }
  constexpr long abs(const long x) {
    return x < 0 ? -x : x;
  }
  constexpr long long abs(const long long x) {
    return x < 0 ? -x : x;
  }
  constexpr unsigned int abs(const unsigned int x) {
    return x;
  }
  constexpr unsigned long abs(const unsigned long x) {
    return x;
  }
  constexpr unsigned long long abs(const unsigned long long x) {
    return x;
  }
}


#line 9 "tools/extgcd.hpp"

namespace tools {

  template <typename T>
  ::std::tuple<T, T, T> extgcd(T prev_r, T r) {
    const bool prev_r_is_neg = prev_r < T(0);
    const bool r_is_neg = r < T(0);

    if (prev_r_is_neg) prev_r = -prev_r;
    if (r_is_neg) r = -r;

    #ifndef NDEBUG
    const T a = prev_r;
    const T b = r;
    #endif

    T prev_s(1);
    T prev_t(0);
    T s(0);
    T t(1);
    while (r != T(0)) {
      const T q = prev_r / r;
      ::std::tie(prev_r, r) = ::std::make_pair(r, prev_r - q * r);
      ::std::tie(prev_s, s) = ::std::make_pair(s, prev_s - q * s);
      ::std::tie(prev_t, t) = ::std::make_pair(t, prev_t - q * t);
    }

    if (prev_r_is_neg) prev_s = -prev_s;
    if (r_is_neg) prev_t = -prev_t;

    assert(::tools::abs(prev_s) <= ::std::max(b / prev_r / T(2), T(1)));
    assert(::tools::abs(prev_t) <= ::std::max(a / prev_r / T(2), T(1)));
    return ::std::make_tuple(prev_s, prev_t, prev_r);
  }
}


#line 5 "tests/extgcd.test.cpp"

using ll = long long;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  ll a, b;
  std::cin >> a >> b;

  const auto [x0, y0, gcd] = tools::extgcd(a, b);
  std::cout << x0 << ' ' << y0 << '\n';

  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	5 ms	4 MB
g++	00_sample_01.in	AC	4 ms	4 MB
g++	01_small_00.in	AC	4 ms	4 MB
g++	01_small_01.in	AC	4 ms	4 MB
g++	01_small_02.in	AC	4 ms	4 MB
g++	01_small_03.in	AC	4 ms	4 MB
g++	01_small_04.in	AC	4 ms	4 MB
g++	01_small_05.in	AC	4 ms	4 MB
g++	02_critical_00.in	AC	4 ms	4 MB
g++	02_critical_01.in	AC	4 ms	4 MB
g++	02_critical_02.in	AC	4 ms	4 MB
g++	02_critical_03.in	AC	4 ms	4 MB
g++	03_large_00.in	AC	4 ms	4 MB
g++	03_large_01.in	AC	4 ms	4 MB
g++	03_large_02.in	AC	4 ms	4 MB
g++	03_large_03.in	AC	4 ms	4 MB
g++	03_large_04.in	AC	4 ms	4 MB
g++	03_large_05.in	AC	4 ms	4 MB
g++	03_large_06.in	AC	4 ms	4 MB
g++	03_large_07.in	AC	4 ms	4 MB
g++	03_large_08.in	AC	4 ms	4 MB
g++	03_large_09.in	AC	4 ms	4 MB
g++	04_corner_00.in	AC	4 ms	4 MB
g++	04_corner_01.in	AC	4 ms	4 MB
g++	04_corner_02.in	AC	4 ms	4 MB
g++	04_corner_03.in	AC	4 ms	4 MB
g++	05_rand_00.in	AC	4 ms	4 MB
g++	05_rand_01.in	AC	4 ms	4 MB
g++	05_rand_02.in	AC	4 ms	4 MB
g++	05_rand_03.in	AC	4 ms	4 MB
g++	05_rand_04.in	AC	4 ms	4 MB
g++	05_rand_05.in	AC	4 ms	4 MB

Back to top page