change extended euclid

1 files changed, 4 insertions, 5 deletions

diff --git a/math/extendedEuclid.cpp b/math/extendedEuclid.cpp
index d016a63..ecf4a16 100644
--- a/math/extendedEuclid.cpp
+++ b/math/extendedEuclid.cpp
@@ -1,7 +1,6 @@
 // a*x + b*y = ggt(a, b)
-ll extendedEuclid(ll a, ll b, ll& x, ll& y) {
-	if (a == 0) {x = 0; y = 1; return b;}
-	ll x1, y1, d = extendedEuclid(b % a, a, x1, y1);
-	x = y1 - (b / a) * x1; y = x1;
-	return d;
+array<ll, 3> extendedEuclid(ll a, ll b) {
+	if (a == 0) return {b, 0, 1};
+	auto [d, x, y] = extendedEuclid(b % a, a);
+	return {d, y - (b / a) * x, x};
 }