Test/AOJ/NTL_1_E.test.cpp

View this file on GitHub
Last update: 2024-11-29 05:08:07+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_E

Depends on

拡張ユークリッドの互除法 (Src/Number/ExtendGCD.hpp)

Code

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

#include "../../Src/Number/ExtendGCD.hpp"

#include <iostream>

int main() {
    int a, b;
    std::cin >> a >> b;
    auto [x, y]{zawa::ExtendGCD(a, b)};
    std::cout << x << ' ' << y << '\n';
}

#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"

#line 2 "Src/Number/ExtendGCD.hpp"

#include <utility>

namespace zawa {

template <class T>
std::pair<T, T> ExtendGCD(T a, T b) {
    if (a == 0) return { T{0}, 1 };
    if (b == 0) return { T{1}, 0 };
    T px{1}, py{0}, x{0}, y{1};
    while (a % b) {
        T d{a / b}, r{a % b};
        T nx{px - d*x}, ny{py - d*y};
        px = x;
        py = y;
        x = nx;
        y = ny;
        a = b;
        b = r;
    }
    return {x, y};
}

} // namespace zawa
#line 4 "Test/AOJ/NTL_1_E.test.cpp"

#include <iostream>

int main() {
    int a, b;
    std::cin >> a >> b;
    auto [x, y]{zawa::ExtendGCD(a, b)};
    std::cout << x << ' ' << y << '\n';
}