1 files changed, 11 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