diff options
Diffstat (limited to 'math/extendedEuclid.cpp')
| -rw-r--r-- | math/extendedEuclid.cpp | 9 |
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}; } |