| # | Likes | Tech tags | Title | Creator | Created date |
|---|---|---|---|---|---|
| 1 | 0 |
2022-11-23 21:36
|
A recursive implementation of the Extended Euclidean algorithm that runs in \(O(\log (a + b))\) time
#include <tuple>
std::pair<int, int> extended_euclidean_algorithm(int a, int b) {
if(b == 0) {
return {1, 0};
}
std::pair<int, int> returned = extended_euclidean_algorithm(b, a%b);
return {
returned.second,
returned.first - a/b * returned.second // Integer division is by default towards zero
};
}
int main() {
int x, y;
std::tie(x, y) = extended_euclidean_algorithm(173, 68);
return 0;
}
| functions | ||
std::tie |
en.cppreference.com | cplusplus.com |
| classes | ||
std::pair |
en.cppreference.com | cplusplus.com |
Implement the Extended Euclidean Algorithm. Use it to find \(x\) and \(y\) satisfying the equation \(ax + by = \text{gcd}(a, b)\) for some values of \(a\) and \(b\).