From 8ceb0e35278563a3b315f04fc60fc9086d6c7a8a Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <s_jungeb@i08pc38.atis-stud.uni-karlsruhe.de>
Date: Fri, 14 Nov 2014 15:29:22 +0100
Subject: bellmann ford, gcd, lcm, ectended euclid

---
 math/extendedEuclid.cpp | 11 +++++++++++
 1 file changed, 11 insertions(+)
 create mode 100644 math/extendedEuclid.cpp

(limited to 'math/extendedEuclid.cpp')

diff --git a/math/extendedEuclid.cpp b/math/extendedEuclid.cpp
new file mode 100644
index 0000000..6d9490f
--- /dev/null
+++ b/math/extendedEuclid.cpp
@@ -0,0 +1,11 @@
+//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;
+}
\ No newline at end of file
-- 
cgit v1.2.3