test/AOJ/NTL_1_E.test.cpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E

Depends on

Code

#define PROBLEM                                                                \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E"
#include <bits/stdc++.h>

#include "library/math/ExtraGCD.hpp"

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

    int a, b;
    std::cin >> a >> b;
    auto [x, y] = ext_gcd(a, b);
    std::cout << x << " " << y << std::endl;
}

#line 1 "test/AOJ/NTL_1_E.test.cpp"
#define PROBLEM                                                                \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E"
#include <bits/stdc++.h>

#line 2 "library/math/ExtraGCD.hpp"
using ll = long long;
std::pair<ll, ll> ext_gcd(ll a, ll b) {
    if (b == 0)
        return {1, 0};
    auto [X, Y] = ext_gcd(b, a % b);
    // bX + (a%b)Y = gcd(a,b)
    // a%b = a - b(a/b)
    // ∴ aY + b(X-(a/b)Y) = gcd(a,b)
    ll x = Y, y = X - (a / b) * Y;
    return {x, y};
}
#line 6 "test/AOJ/NTL_1_E.test.cpp"

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

    int a, b;
    std::cin >> a >> b;
    auto [x, y] = ext_gcd(a, b);
    std::cout << x << " " << y << std::endl;
}