verify/aoj-NTL_1_E-extgcd.test.cpp

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_E

Depends on

• 拡張ユークリッドの互除法 (algorithm/Math/NumberTheory/extgcd.hpp)

Code

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

#include <iostream>

#include "../algorithm/Math/NumberTheory/extgcd.hpp"

int main() {
    int a, b;
    std::cin >> a >> b;

    int x, y;
    algorithm::extgcd(a, b, x, y);

    std::cout << x << " " << y << std::endl;
}

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

#include <iostream>

#line 1 "algorithm/Math/NumberTheory/extgcd.hpp"



/**
 * @brief 拡張ユークリッドの互除法
 * @docs docs/Math/NumberTheory/extgcd.md
 */

namespace algorithm {

// 拡張ユークリッドの互除法．
// ax+by=gcd(a,b) を満たす整数の組(x,y)を求め，gcd(a,b)を返す．O(log(min(a,b))).
template <typename Type>
Type extgcd(Type a, Type b, Type &x, Type &y) {
    if(b == 0) {
        x = 1, y = 0;
        return a;
    }
    Type &&d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

}  // namespace algorithm


#line 6 "verify/aoj-NTL_1_E-extgcd.test.cpp"

int main() {
    int a, b;
    std::cin >> a >> b;

    int x, y;
    algorithm::extgcd(a, b, x, y);

    std::cout << x << " " << y << std::endl;
}

Back to top page