test/AOJ/NTL_1_E-Extended-Euclid-Algorithm.test.cpp

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

#include <iostream>

#include "../../Math/Number-Theory/extgcd.hpp"
#include "../../Util/int-alias.hpp"

int main() {
    i64 a, b, x, y;
    std::cin >> a >> b;
    extgcd(a, b, x, y);
    std::cout << x << ' ' << y << std::endl;

    return 0;
}

#line 1 "test/AOJ/NTL_1_E-Extended-Euclid-Algorithm.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E"

#include <iostream>

#line 2 "Math/Number-Theory/extgcd.hpp"

/**
 * @brief extgcd() (拡張ユークリッドの互除法)
 * ax + by = gcd(a, b) の整数解 (x, y) を引数に格納する
 */
template <class T>
T extgcd(T a, T b, T& x, T& y) {
    T g = a;
    if (b != 0) {
        g = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1;
        y = 0;
    }
    return g;
}
#line 2 "Util/int-alias.hpp"
#include <cstdint>

/**
 * @brief int-alias (整数型のエイリアス)
 */
using i64 = int64_t;
using u64 = uint64_t;
#line 7 "test/AOJ/NTL_1_E-Extended-Euclid-Algorithm.test.cpp"

int main() {
    i64 a, b, x, y;
    std::cin >> a >> b;
    extgcd(a, b, x, y);
    std::cout << x << ' ' << y << std::endl;

    return 0;
}