Adding code to count the number of inversions.

4 files changed, 34 insertions, 2 deletions

diff --git a/math/inversions.cpp b/math/inversions.cpp
new file mode 100644
index 0000000..0720407
--- /dev/null
+++ b/math/inversions.cpp
@@ -0,0 +1,27 @@
+// Laufzeit: O(n*log(n))
+ll merge(vector<ll> &v, vector<ll> &left, vector<ll> &right) {
+  int a = 0, b = 0, i = 0;
+  ll inv = 0;
+  while (a < (int)left.size() && b < (int)right.size()) {
+    if (left[a] < right[b]) v[i++] = left[a++];
+    else {
+      inv += left.size() - a;
+      v[i++] = right[b++];
+    }
+  }
+  while (a < (int)left.size()) v[i++] = left[a++];
+  while (b < (int)right.size()) v[i++] = right[b++];
+  return inv;
+}
+
+ll mergeSort(vector<ll> &v) { // Sortiert v und gibt Inversionszahl zurück.
+  int n = v.size();
+  vector<ll> left(n / 2), right((n + 1) / 2);
+  for (int i = 0; i < n / 2; i++) left[i] = v[i];
+  for (int i = n / 2; i < n; i++) right[i - n / 2] = v[i];
+
+  ll result = 0;
+  if (left.size() > 1) result += mergeSort(left);
+  if (right.size() > 1) result += mergeSort(right);
+  return result + merge(v, left, right);
+}
diff --git a/math/math.tex b/math/math.tex
index c02d352..1a4a684 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -120,6 +120,9 @@ Multipliziert Polynome $A$ und $B$.
 \subsection{Longest Increasing Subsequence}
 \lstinputlisting{math/longestIncreasingSubsequence.cpp}
 
+\subsection{Inversionszahl und Mergesort}
+\lstinputlisting{math/inversions.cpp}
+
 \subsection{Satz von \textsc{Sprague-Grundy}}
 Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu:
 \[
diff --git a/math/multInv.cpp b/math/multInv.cpp
index 2aedcd6..4e388b8 100644
--- a/math/multInv.cpp
+++ b/math/multInv.cpp
@@ -2,6 +2,6 @@
 ll multInv(ll n, ll p) {
 	ll x, y;
 	extendedEuclid(n, p, x, y); // Implementierung von oben.
-	x += ((x / p) + 1) * p;
+	x = ((x % p) + p) % p;
 	return x % p;
 }
diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp
index 7e8b288..286aa1d 100644
--- a/math/primeSieve.cpp
+++ b/math/primeSieve.cpp
@@ -1,4 +1,6 @@
 // Laufzeit: O(n * log log n)
+// Kann erweitert werden: Für jede Zahl den kleinsten Primfaktor.
+// Dabei vorsicht: Nicht kleinere Faktoren überschreiben.
 #define N 100000000 // Bis 10^8 in unter 64MB Speicher.
 bitset<N / 2> isNotPrime;
 
@@ -13,7 +15,7 @@ inline int primeSieve() { // Rückgabe: Anzahl der Primzahlen < N.
   int counter = 1; // Die 2, die sonst vergessen würde.
   for (int i = 3; i < N; i += 2) {
     if (!isNotPrime[i / 2]) {
-      for (int j = 3 * i; j < N; j+= 2 * i) isNotPrime[j / 2] = 1;
+      for (int j = i * i; j < N; j+= 2 * i) isNotPrime[j / 2] = 1;
       counter++;
   }}
   return counter;