test/aoj/ntl_1_e.test.cpp

View this file on GitHub
Last update: 2022-12-18 20:53:53+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_E

Depends on

src/math/ext_gcd.hpp

Code

#define PROBLEM                                                                \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_E"

#include <bits/stdc++.h>
using namespace std;

#include "../../src/math/ext_gcd.hpp"

int main() {
  int a, b;
  cin >> a >> b;
  int x, y;
  ext_gcd(a, b, x, y);
  cout << x << " " << y << endl;
  return 0;
}

#line 1 "test/aoj/ntl_1_e.test.cpp"
#define PROBLEM                                                                \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_E"

#include <bits/stdc++.h>
using namespace std;

#line 2 "src/math/ext_gcd.hpp"

#line 4 "src/math/ext_gcd.hpp"
using namespace std;

template <typename T = long long> T ext_gcd(T a, T b, T &x, T &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = ext_gcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
#line 8 "test/aoj/ntl_1_e.test.cpp"

int main() {
  int a, b;
  cin >> a >> b;
  int x, y;
  ext_gcd(a, b, x, y);
  cout << x << " " << y << endl;
  return 0;
}