From 0a1fd7ed34e3a15f6ac3f646d30c9f0b6db5d3ed Mon Sep 17 00:00:00 2001 From: Yidi Date: Fri, 22 Mar 2024 12:21:09 +0100 Subject: change extended euclid --- math/extendedEuclid.cpp | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-) (limited to 'math/extendedEuclid.cpp') 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 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}; } -- cgit v1.2.3