Extended Euclidean algorithm
(Mylib/Number/extended_gcd.cpp)
Operations
Requirements
Notes
Problems
References
Required by
Verified with
Code
#pragma once
#include <tuple>
namespace haar_lib {
auto ext_gcd(int64_t a, int64_t b) -> std::tuple<
int64_t, // gcd
int64_t, // p
int64_t // q
> {
if (b == 0) return std::make_tuple(a, 1, 0);
const auto [d, q, p] = ext_gcd(b, (a + b) % b);
return std::make_tuple(d, p, q - a / b * p);
}
} // namespace haar_lib
#line 2 "Mylib/Number/extended_gcd.cpp"
#include <tuple>
namespace haar_lib {
auto ext_gcd(int64_t a, int64_t b) -> std::tuple<
int64_t, // gcd
int64_t, // p
int64_t // q
> {
if (b == 0) return std::make_tuple(a, 1, 0);
const auto [d, q, p] = ext_gcd(b, (a + b) % b);
return std::make_tuple(d, p, q - a / b * p);
}
} // namespace haar_lib
Back to top page