test/extgcd.aoj.NTL_1_E.test.cpp

View this file on GitHub
Last update: 2020-05-10 11:45:22+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/all/NTL_1_E

Depends on

lib/extgcd.hpp

Code

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

#include <iostream>
#include "../lib/extgcd.hpp"

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

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

#include <iostream>
#line 1 "lib/extgcd.hpp"



#include <tuple>
#include <utility>

// Find x and y such that a*x + b*y = gcd(a, b)
// Return gcd(a, b)
long long extgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    long long ret = extgcd(b, a%b, x, y);
    std::tie(x, y) = std::make_pair(y, x - a / b * y);
    return ret;
}


#line 5 "test/extgcd.aoj.NTL_1_E.test.cpp"

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