test/aoj_ntl_1_e.test.cpp

View this file on GitHub
Last update: 2022-08-15 02:43:26+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_E

Depends on

Extend GCD (拡張ユークリッドの互除法) (src/math/Extend-GCD.hpp)

Code

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

#include <iostream>
#include "../src/math/Extend-GCD.hpp"

int main() {
    int a, b;
    std::cin >> a >> b;
    auto [x, y] = zawa::extend_gcd(a, b);
    std::cout << x << ' ' << y << std::endl;
}

#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 <iostream>
#line 2 "src/math/Extend-GCD.hpp"

namespace zawa {

    void rec(long long a, long long b, long long& x, long long& y) {
        if (b == 0) {
            x = 1;
            y = 0;
            return;
        }

        rec(b, a % b, y, x);
        
        y -= a / b * x;
    }

    std::pair<long long, long long> extend_gcd(long long a, long long b) {
        long long resx = 0, resy = 0;
        rec(a, b, resx, resy);
        return {resx, resy};
    }

}// namespace zawa
#line 5 "test/aoj_ntl_1_e.test.cpp"

int main() {
    int a, b;
    std::cin >> a >> b;
    auto [x, y] = zawa::extend_gcd(a, b);
    std::cout << x << ' ' << y << std::endl;
}