verify/aoj_ntl/aoj_ntl_1_e.test.cpp

View this file on GitHub
Last update: 2024-02-23 10:46:31+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E

Depends on

math/extended_gcd.hpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E"

#include <bits/stdc++.h>

#include "math/extended_gcd.hpp"

int main() {
    long long a, b;
    std::cin >> a >> b;
    auto [x, y, g] = extended_gcd(a, b);
    std::cout << x << ' ' << y << '\n';
    return 0;
}

#line 1 "verify/aoj_ntl/aoj_ntl_1_e.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E"

#include <bits/stdc++.h>

#line 2 "math/extended_gcd.hpp"

#line 4 "math/extended_gcd.hpp"
// find (x, y) s.t. ax + by = gcd(a, b)
// a, b >= 0
// return {x, y, gcd(a, b)}
template <class T> std::tuple<T, T, T> extended_gcd(T a, T b) {
    if (b == 0) return {1, 0, a};
    auto [y, x, g] = extended_gcd(b, a % b);
    return {x, y - (a / b) * x, g};
}
#line 6 "verify/aoj_ntl/aoj_ntl_1_e.test.cpp"

int main() {
    long long a, b;
    std::cin >> a >> b;
    auto [x, y, g] = extended_gcd(a, b);
    std::cout << x << ' ' << y << '\n';
    return 0;
}