math/extended_gcd.hpp

• View this file on GitHub
• Last update: 2024-02-23 10:34:07+09:00
• Include: #include "math/extended_gcd.hpp"

Required by

• math/baby_step_giant_step.hpp
• Chinese Remainder Theorem (中国剰余定理) (math/chinese_remainder_theorem.hpp)
• math/inv_mod.hpp
• 線形ディオファントス方程式 ($ ax + by = c $) / 線形合同式 ( $ ax \equiv b \pmod m $ ) (math/linear_diophantine.hpp)

Verified with

• verify/aoj_ntl/aoj_ntl_1_e.test.cpp
• verify/yuki/yuki_186_chinese_remainder_theorem.test.cpp

Code

#pragma once

#include <tuple>
// find (x, y) s.t. ax + by = gcd(a, b)
// a, b >= 0
// return {x, y, gcd(a, b)}
template <class T> std::tuple<T, T, T> extended_gcd(T a, T b) {
    if (b == 0) return {1, 0, a};
    auto [y, x, g] = extended_gcd(b, a % b);
    return {x, y - (a / b) * x, g};
}

#line 2 "math/extended_gcd.hpp"

#include <tuple>
// find (x, y) s.t. ax + by = gcd(a, b)
// a, b >= 0
// return {x, y, gcd(a, b)}
template <class T> std::tuple<T, T, T> extended_gcd(T a, T b) {
    if (b == 0) return {1, 0, a};
    auto [y, x, g] = extended_gcd(b, a % b);
    return {x, y - (a / b) * x, g};
}

Back to top page