From f5316545b46edfc511b628430cd883ca2c56f1ca Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 8 Oct 2016 23:06:01 +0200 Subject: New extended euclid code without global variables. --- math/extendedEuclid.cpp | 15 +++++---------- 1 file changed, 5 insertions(+), 10 deletions(-) (limited to 'math/extendedEuclid.cpp') diff --git a/math/extendedEuclid.cpp b/math/extendedEuclid.cpp index 65d6ed9..66a6d93 100644 --- a/math/extendedEuclid.cpp +++ b/math/extendedEuclid.cpp @@ -1,11 +1,6 @@ -// Accepted in Aufgabe mit Forderung: |X|+|Y| minimal (primaer) und X<=Y (sekundaer). -// Hab aber keinen Beweis dafuer :) -ll x, y, d; // a * x + b * y = d = ggT(a,b) -void extendedEuclid(ll a, ll b) { - if (!b) { - x = 1; y = 0; d = a; return; - } - extendedEuclid(b, a % b); - ll x1 = y; ll y1 = x - (a / b) * y; - x = x1; y = y1; +ll extendedEuclid(ll a, ll b, ll &x, ll &y) { // a*x + b*y = ggt(a, b). + 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; } -- cgit v1.2.3