Verify/extended_gcd.test.cpp

• View this file on GitHub
• Last update: 2020-07-26 22:31:04+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/all/NTL_1_E

Depends on

• Number/extended_gcd.hpp

Code

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

#include "../Number/extended_gcd.hpp"

#include <iostream>
#include <cassert>

int main() {
    std::cin.tie();
    std::ios::sync_with_stdio(false);

    int a, b;
    std::cin >> a >> b;

    int x, y;
    int g = extgcd(a, b, x, y);
    assert(a * x + b * y == g);

    std::cout << x << " " << y << "\n";
    return 0;
}

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

#line 2 "Number/extended_gcd.hpp"

#include <algorithm>

template <typename T>
T extgcd(T a, T b, T& x, T& y) {
    T s = a, t = b,
      xs = 1, ys = 0,
      xt = 0, yt = 1;

    while (t != 0) {
        T div = s / t;

        s -= t * div;
        xs -= xt * div;
        ys -= yt * div;

        std::swap(s, t);
        std::swap(xs, xt);
        std::swap(ys, yt);
    }

    x = xs;
    y = ys;
    return s;
}
#line 4 "Verify/extended_gcd.test.cpp"

#include <iostream>
#include <cassert>

int main() {
    std::cin.tie();
    std::ios::sync_with_stdio(false);

    int a, b;
    std::cin >> a >> b;

    int x, y;
    int g = extgcd(a, b, x, y);
    assert(a * x + b * y == g);

    std::cout << x << " " << y << "\n";
    return 0;
}

Back to top page