test/math/extgcd.test.cpp

View this file on GitHub
Last update: 2026-01-09 14:45:55+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_E

Depends on

Extended Euclidean Algorithm (math/extgcd.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_E"

#include "math/extgcd.hpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int a, b;
    std::cin >> a >> b;
    int x, y;
    extgcd(a, b, x, y);
    std::cout << x << " " << y << "\n";
}

#line 1 "test/math/extgcd.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_E"

#line 1 "math/extgcd.hpp"



template <typename T> T extgcd(T a, T b, T &x, T &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    T d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}


#line 4 "test/math/extgcd.test.cpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int a, b;
    std::cin >> a >> b;
    int x, y;
    extgcd(a, b, x, y);
    std::cout << x << " " << y << "\n";
}