Extgcd (extended Euclidean algorithm) (library/math/extgcd.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-03-15 16:42:38+06:00
• Include: #include "library/math/extgcd.hpp"

extgcd

T extgcd(T a, T b, T &x, T &y)

for $\gcd(a, b)$ returns $(x, y)$. Contains integer solutions that satisfy $ax + by = \gcd(a, b)$. If multiple integer solutions are possible, the one with the smallest $|x| + |y|$ is stored.

Constraint

• $1 \leq a, b$

Complexity

• $O(\log {\min(a, b)})$

Verified with

• library/test/aoj/NTL_1_E-Extended_Euclid_Algorithm.test.cpp

Code

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;
}

#line 1 "library/math/extgcd.hpp"
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;
}

Back to top page