math/extGcd.cpp

• View this file on GitHub
• Last update: 2021-03-07 15:45:48+09:00

Verified with

• test/extGcd.test.cpp

Code

#pragma once
#include <tuple>

template <class T> T extGcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extGcd(b, a % b, y, x);
		y -= (a / b) * x;
	} else {
		x = 1;
		y = 0;
	}
	return d;
}

template <class T> std::tuple<T, T, T> extGcd(T a, T b) {
	T x, y;
	T gcd = extGcd(a, b, x, y);
	return {gcd, x, y};
}

#line 2 "math/extGcd.cpp"
#include <tuple>

template <class T> T extGcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extGcd(b, a % b, y, x);
		y -= (a / b) * x;
	} else {
		x = 1;
		y = 0;
	}
	return d;
}

template <class T> std::tuple<T, T, T> extGcd(T a, T b) {
	T x, y;
	T gcd = extGcd(a, b, x, y);
	return {gcd, x, y};
}

Back to top page