bellmann ford, gcd, lcm, ectended euclid

3 files changed, 22 insertions, 0 deletions

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
diff --git a/math/gcd-lcm.cpp b/math/gcd-lcm.cpp
new file mode 100644
index 0000000..3a0f742
--- /dev/null
+++ b/math/gcd-lcm.cpp
@@ -0,0 +1,7 @@
+ll gcd(ll a, ll b) {
+	return b == 0 ? a : gcd (b, a % b);
+}
+
+ll lcm(ll a, ll b) {
+	return a * (b / gcd(a, b)); //Klammern gegen Overflow
+}
\ No newline at end of file
diff --git a/math/math.tex b/math/math.tex
index e1e0950..0b66163 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -1,4 +1,8 @@
 \section{Mathe}
 
+\subsection{ggT, kgV, erweiterter euklidischer Algorithmus}
+\lstinputlisting{math/gcd-lcm.cpp}
+\lstinputlisting{math/extendedEuclid.cpp}
+
 \subsection{Binomialkoeffizienten}
 \lstinputlisting{math/binomial.cpp}
\ No newline at end of file