Math section rebuild, merged convinience and sonstiges section.

12 files changed, 164 insertions, 111 deletions

diff --git a/math/binomial.cpp b/math/binomial.cpp
index 61d9d69..a8f1561 100644
--- a/math/binomial.cpp
+++ b/math/binomial.cpp
@@ -1,10 +1,10 @@
-ll calc_binom(ll N, ll K) {
+// Laufzeit: O(k)
+ll calc_binom(ll n, ll k) {
    ll r = 1, d;
-   if (K > N) return 0;
-   for (d = 1; d <= K; d++) {
-      r *= N--;
+   if (k > n) return 0;
+   for (d = 1; d <= k; d++) {
+      r *= n--;
       r /= d;
    }
    return r;
 }
-
diff --git a/math/chineseRemainder.cpp b/math/chineseRemainder.cpp
new file mode 100644
index 0000000..5d06743
--- /dev/null
+++ b/math/chineseRemainder.cpp
@@ -0,0 +1,36 @@
+// Laufzeit: O(n * log(n)), n := Anzahl der Kongruenzen
+// Nur für teilerfremde Moduli.
+// Berechnet das kleinste, nicht negative x, das die Kongruenzen simultan löst.
+// Alle Lösungen sind kongruent zum kgV der Moduli (Produkt, falls alle teilerfremd sind).
+struct ChineseRemainder {
+	typedef __int128 lll;
+	vector<lll> lhs, rhs, module, inv;
+	lll M; // Produkt über die Moduli. Kann leicht überlaufen.
+
+	ll g(vector<lll> &vec) {
+		lll res = 0;
+		for (int i = 0; i < (int)vec.size(); i++) {
+			res += (vec[i] * inv[i]) % M;
+			res %= M;
+		}
+		return res;
+	}
+
+	// Fügt Kongruenz l * x = b (mod m) hinzu.
+	void addEquation(ll l, ll r, ll m) {
+		lhs.push_back(l);
+		rhs.push_back(r);
+		module.push_back(m);
+	}
+
+	// Löst das System.
+	ll solve() {
+		M = accumulate(module.begin(), module.end(), lll(1), multiplies<lll>());
+		inv.resize(lhs.size());
+		for (int i = 0; i < (int)lhs.size(); i++) {
+			lll x = (M / module[i]) % module[i];
+			inv[i] = (multInvers(x, module[i]) * (M / module[i]));
+		}
+		return (multInvers(g(lhs), M) * g(rhs)) % M;
+	}
+};
diff --git a/math/extendedEuclid.cpp b/math/extendedEuclid.cpp
index 6d9490f..65d6ed9 100644
--- a/math/extendedEuclid.cpp
+++ b/math/extendedEuclid.cpp
@@ -1,6 +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)
+// 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;
@@ -8,4 +8,4 @@ void extendedEuclid(ll a, ll b) {
 	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/factor.cpp b/math/factor.cpp
deleted file mode 100644
index 621d057..0000000
--- a/math/factor.cpp
+++ /dev/null
@@ -1,20 +0,0 @@
-typedef pair<int,int> ii;
-//Factorize a number n in its prime factors
-//Call primeSieve-method before with N > sqrt(n)
-//Return: Returns a vector of pairs, where the first entry in the pair is
-//the prime factor p and the second counts how many times p divides n
-vector<ii> factorize(ll n) {
-  vector<ii> fact; ll num = n, i = 0, c = 0;
-  while(num != 1) {
-    if(num % primes[i] == 0) {
-      c++; num /= primes[i];
-    } else {
-      if(c > 0)
-	      fact.push_back(make_pair(primes[i],c));
-      i++; c = 0;
-      if(primes[i]*primes[i] > num) break;
-    }
-  }
-  if(num != 1) fact.push_back(make_pair(num,c+1));
-  return fact;
-}
\ No newline at end of file
diff --git a/math/gcd-lcm.cpp b/math/gcd-lcm.cpp
index 3a0f742..10ecb3d 100644
--- a/math/gcd-lcm.cpp
+++ b/math/gcd-lcm.cpp
@@ -1,7 +1,8 @@
+// Laufzeiten: O(log(a) + log(b))
 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
+	return a * (b / gcd(a, b)); // Klammern gegen Overflow.
+}
diff --git a/math/lgsFp.cpp b/math/lgsFp.cpp
index e42e4ab..439e5b7 100644
--- a/math/lgsFp.cpp
+++ b/math/lgsFp.cpp
@@ -1,15 +1,16 @@
-void normalLine(ll n, ll line, ll p) { //normalisiert Zeile line
-	ll factor = multInv(mat[line][line], p); //Implementierung von oben
+// Laufzeit: O(n^3)
+void normalLine(ll n, ll line, ll p) { // Normalisiert Zeile line.
+	ll factor = multInv(mat[line][line], p); // Implementierung von oben.
 	for (ll i = 0; i <= n; i++) {
 		mat[line][i] *= factor;
 		mat[line][i] %= p;
 	}
 }
 
-void takeAll(ll n, ll line, ll p) { //zieht Vielfaches von line von allen anderen Zeilen ab
+void takeAll(ll n, ll line, ll p) { // Zieht Vielfaches von line von allen anderen Zeilen ab.
 	for (ll i = 0; i < n; i++) {
 		if (i == line) continue;
-		ll diff = mat[i][line]; //abziehen
+		ll diff = mat[i][line];
 		for (ll j = 0; j <= n; j++) {
 			mat[i][j] -= (diff * mat[line][j]) % p;
 			while (mat[i][j] < 0) {
@@ -19,9 +20,9 @@ void takeAll(ll n, ll line, ll p) { //zieht Vielfaches von line von allen andere
 	}
 }
 
-void gauss(ll n, ll p) { //n x n+1-Matrix, Koerper F_p
+void gauss(ll n, ll p) { // nx(n+1)-Matrix, Koerper F_p.
 	for (ll line = 0; line < n; line++) {
 		normalLine(n, line, p);
 		takeAll(n, line, p);
 	}
-}
\ No newline at end of file
+}
diff --git a/math/math.tex b/math/math.tex
index 59219e5..b0ff8da 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -5,59 +5,66 @@
 \lstinputlisting{math/extendedEuclid.cpp}
 
 \subsubsection{Multiplikatives Inverses von $x$ in $\mathbb{Z}/n\mathbb{Z}$}
-Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$.
+Sei $0 \leq x < n$. Definiere $d := \gcd(x, n)$.
 \begin{description}
 	\item[Falls $d = 1$:] ~
 	\begin{itemize}[nosep]
-		\item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit $\alpha x + \beta n = 1$
-		\item Nach Kongruenz gilt $\alpha x + \beta n \equiv \alpha x \equiv 1 \mod n$
+		\item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit
+		$\alpha x + \beta n = 1$.
+		\item Nach Kongruenz gilt $\alpha x + \beta n \equiv \alpha x \equiv 1 \mod n$.
 		\item $x^{-1} :\equiv \alpha \mod n$
 	\end{itemize}
-	\item[Falls $d \neq 1$:] es existiert kein $x^{-1}$
+	\item[Falls $d \neq 1$:] Es existiert kein $x^{-1}$.
 \end{description}
 \lstinputlisting{math/multInv.cpp}
 
-\subsection{Primzahlsieb von \textsc{Eratosthenes}}
-\lstinputlisting{math/primeSieve.cpp}
-
-\subsection{\textsc{Miller}-\textsc{Rabin}-Primzahltest}
-\lstinputlisting{math/millerRabin.cpp}
-
-\subsection{Faktorisierung}
-\lstinputlisting{math/factor.cpp}
-
 \subsection{Mod-Exponent über $\mathbb{F}_p$}
 \lstinputlisting{math/modExp.cpp}
 
 \subsection{LGS über $\mathbb{F}_p$}
 \lstinputlisting{math/lgsFp.cpp}
 
+\subsection{Chinesischer Restsatz}
+\begin{itemize}
+	\item Extrem anfällig gegen Overflows. Evtl. häufig 128-Bit Integer verwenden.
+	\item Direkte Formel für zwei Kongruenzen $x \equiv a \mod n$, $x \equiv b \mod m$:
+		\[
+			x \equiv a - y * n * \frac{a - b}{d} \mod \frac{mn}{d}
+			\qquad \text{mit} \qquad
+			d := ggT(n, m) = yn + zm
+		\]
+		Formel kann auch für nicht teilerfremde Moduli verwendet werden.
+	\item Sind die Moduli nicht teilerfremd, existiert genau dann eine Lösung,
+	wenn $a_i \equiv a_j \mod \gcd(m_i, m_j)$. In diesem Fall sind keine Faktoren
+	auf der linken Seite erlaubt.
+\end{itemize}
+\lstinputlisting{math/chineseRemainder.cpp}
+
+\subsection{Primzahlsieb von \textsc{Eratosthenes}}
+\lstinputlisting{math/primeSieve.cpp}
+
+\subsection{\textsc{Miller}-\textsc{Rabin}-Primzahltest}
+\lstinputlisting{math/millerRabin.cpp}
+
 \subsection{Binomialkoeffizienten}
+Vorberechnen, wenn häufig benötigt.
 \lstinputlisting{math/binomial.cpp}
 
-\subsection{Satz von \textsc{Sprague-Grundy}}
-Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu:
-\[
-	g\left(X\right) := \min\{ \mathbb{Z}_0^+ \textbackslash \{g\left(Y\right)~|~Y \text{ von } X \text{ aus direkt erreichbar}\}\} 
-\]
-$X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\\\
-Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$.
-\lstinputlisting{math/nimm.cpp}
-
 \subsection{Maximales Teilfeld}
 \lstinputlisting{math/maxTeilfeld.cpp}
 Obiger Code findet kein maximales Teilfeld, das über das Ende hinausgeht. Dazu:
 \begin{enumerate}
-	\item finde maximales Teilfeld, das nicht übers Ende geht
-	\item berechne minimales Teilfeld, das nicht über den Rand geht (analog)
-	\item nimm Maximum aus gefundenem Maximalem und Allem\textbackslash Minimalem
+	\item Finde maximales Teilfeld, das nicht übers Ende geht.
+	\item Berechne minimales Teilfeld, das nicht über den Rand geht (analog).
+	\item Nimm Maximum aus gefundenem Maximalen und Allem ohne dem Minimalen.
 \end{enumerate}
 
 \subsection{Polynome \& FFT}
 Multipliziert Polynome $A$ und $B$.
 \begin{itemize}
 	\item $\deg(A * B) = \deg(A) + \deg(B)$
-	\item Vektoren \lstinline{a} und \lstinline{b} müssen mindestens Größe $\deg(A * B) + 1$ haben.
+	\item Vektoren \lstinline{a} und \lstinline{b} müssen mindestens Größe
+	$\deg(A * B) + 1$ haben.
 	Größe muss eine Zweierpotenz sein.
 	\item Für ganzzahlige Koeffizienten: \lstinline{(int)round(real(a[i]))}
 \end{itemize}
@@ -76,7 +83,8 @@ Multipliziert Polynome $A$ und $B$.
 
 	\textsc{Catalan}-Zahlen	&
 	$C_0 = 1 \qquad
-	C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} = \frac{1}{n + 1}\binom{2n}{n} = \frac{2(2n - 1)}{n+1} \cdot C_{n-1}$ &
+	C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} =
+	\frac{1}{n + 1}\binom{2n}{n} = \frac{2(2n - 1)}{n+1} \cdot C_{n-1}$ &
 	Bem. \ref{bem:catalanOverflow}, \ref{bem:catalanAnwendung} \\
 
 	\textsc{Euler}-Zahlen (I) &
@@ -102,82 +110,107 @@ Multipliziert Polynome $A$ und $B$.
 	Bem. \ref{bem:stirling2} \\
 
 	Integer-Partitions &
-	$f(1,1) = 1 \qquad f(n,k) = 0 \text{ für } k > n \qquad f(n,k)  = f(n-k,k) + f(n,k-1)$ &
+	$f(1,1) = 1 \qquad f(n,k) = 0 \text{ für } k > n \qquad f(n,k)  =
+	f(n-k,k) + f(n,k-1)$ &
 	Bem. \ref{bem:integerPartitions} \\
 	\hline
 \end{tabularx}
 
 \begin{bem}\label{bem:fibonacciMat}
-$
-\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^n
-\cdot
-\begin{pmatrix} 0 \\ 1 \end{pmatrix}
-=
-\begin{pmatrix}f_n \\ f_{n+1} \end{pmatrix}
-$
+	$
+	\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^n
+	\cdot
+	\begin{pmatrix} 0 \\ 1 \end{pmatrix}
+	=
+	\begin{pmatrix}f_n \\ f_{n+1} \end{pmatrix}
+	$
 \end{bem}
 
 \begin{bem}[\textsc{Zeckendorfs} Theorem]\label{bem:fibonacciGreedy}
-Jede positive natürliche Zahl kann eindeutig als Summe einer oder mehrerer verschiedener \textsc{Fibonacci}-Zahlen geschrieben werden, sodass keine zwei aufeinanderfolgenden \textsc{Fibonacci}-Zahlen in der Summe vorkommen.
+	Jede positive natürliche Zahl kann eindeutig als Summe einer oder mehrerer
+	verschiedener \textsc{Fibonacci}-Zahlen geschrieben werden, sodass keine zwei
+	aufeinanderfolgenden \textsc{Fibonacci}-Zahlen in der Summe vorkommen.
 
-\emph{Lösung: } Greedy, nimm immer die größte \textsc{Fibonacci}-Zahl, die noch hineinpasst.
+	\emph{Lösung:} Greedy, nimm immer die größte \textsc{Fibonacci}-Zahl, die noch
+	hineinpasst.
 \end{bem}
 
 \begin{bem}\label{bem:catalanOverflow}
-\begin{itemize}
-	\item Die erste und dritte angegebene Formel sind relativ sicher gegen Overflows.
-	\item Die erste Formel kann auch zur Berechnung der \textsc{Catalan}-Zahlen bezüglich eines Moduls genutzt werden.
-\end{itemize}
+	\begin{itemize}
+		\item Die erste und dritte angegebene Formel sind relativ sicher gegen Overflows.
+		\item Die erste Formel kann auch zur Berechnung der \textsc{Catalan}-Zahlen
+		bezüglich eines Moduls genutzt werden.
+	\end{itemize}
 \end{bem}
 
 \begin{bem}\label{bem:catalanAnwendung}
-Die \textsc{Catalan}-Zahlen geben an: $C_n =$
-\begin{itemize}
-	\item Anzahl der Binärbäume mit $n$ Knoten
-	\item Anzahl der validen Klammerausdrücke mit $n$ Klammerpaaren
-	\item Anzahl der korrekten Klammerungen von $n+1$ Faktoren
-	\item Anzahl der Möglichkeiten ein konvexes Polygon mit $n+2$ Ecken in Dreiecke zu zerlegen.
-	\item Anzahl der monotonen Pfade in einem $n \times n$-Gitter, die nicht die Diagonale kreuzen. (zwischen gegenüberliegenden Ecken)
-\end{itemize}
+	Die \textsc{Catalan}-Zahlen geben an: $C_n =$
+	\begin{itemize}
+		\item Anzahl der Binärbäume mit $n$ nicht unterscheidbaren Knoten.
+		\item Anzahl der validen Klammerausdrücke mit $n$ Klammerpaaren.
+		\item Anzahl der korrekten Klammerungen von $n+1$ Faktoren.
+		\item Anzahl der Möglichkeiten ein konvexes Polygon mit $n + 2$ Ecken in
+		Dreiecke zu zerlegen.
+		\item Anzahl der monotonen Pfade (zwischen gegenüberliegenden Ecken) in
+		einem $n \times n$-Gitter, die nicht die Diagonale kreuzen.
+	\end{itemize}
 \end{bem}
 
 \begin{bem}[\textsc{Euler}-Zahlen 1. Ordnung]\label{bem:euler1}
-Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Anstiegen.
+	Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Anstiegen.
 
-Begründung: Für die $n$-te Zahl gibt es $n$ mögliche Positionen zum Einfügen. Dabei wird entweder ein Ansteig in zwei gesplitted oder ein Anstieg um $n$ ergänzt.
-\end{bem}
+	Begründung: Für die $n$-te Zahl gibt es $n$ mögliche Positionen zum Einfügen.
+	Dabei wird entweder ein Ansteig in zwei gesplitted oder ein Anstieg um $n$ ergänzt.
+	\end{bem}
 
 \begin{bem}[\textsc{Euler}-Zahlen 2. Ordnung]\label{bem:euler2}
-Die Anzahl der Permutationen von $\{1,1, \ldots, n,n\}$ mit genau $k$ Anstiegen.
+	Die Anzahl der Permutationen von $\{1,1, \ldots, n,n\}$ mit genau $k$ Anstiegen.
 \end{bem}
 
 \begin{bem}[\textsc{Stirling}-Zahlen 1. Ordnung]\label{bem:stirling1}
-Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Zyklen.
+	Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Zyklen.
 
-Begründung: Es gibt zwei Möglichkeiten für die $n$-te Zahl. Entweder sie bildet einen eigene Zyklus, oder sie kann an jeder Position in jedem Zyklus einsortiert werden.
+	Begründung: Es gibt zwei Möglichkeiten für die $n$-te Zahl. Entweder sie
+	bildet einen eigene Zyklus, oder sie kann an jeder Position in jedem Zyklus
+	einsortiert werden.
 \end{bem}
 
 \begin{bem}[\textsc{Stirling}-Zahlen 2. Ordnung]\label{bem:stirling2}
-Die Anzahl der Möglichkeiten $n$ Elemente in $k$ nichtleere Teilmengen zu zerlegen.
+	Die Anzahl der Möglichkeiten $n$ Elemente in $k$ nichtleere Teilmengen zu zerlegen.
 
-Begründung: Es gibt $k$ Möglichkeiten die $n$ in eine $n-1$-Partition einzuordnen. Dazu kommt der Fall, dass die $n$ in ihrer eigenen Teilmenge (alleine) steht.
+	Begründung: Es gibt $k$ Möglichkeiten die $n$ in eine $n-1$-Partition
+	einzuordnen. Dazu kommt der Fall, dass die $n$ in ihrer eigenen Teilmenge
+	(alleine) steht.
 \end{bem}
 
 \begin{bem}\label{bem:integerPartitions}
-Anzahl der Teilmengen von $\mathbb{N}$, die sich zu $n$ aufaddieren mit maximalem Elment $\leq k$.
+	Anzahl der Teilmengen von $\mathbb{N}$, die sich zu $n$ aufaddieren mit
+	maximalem Elment $\leq k$.
 \end{bem}
 
 \subsubsection{Verschiedenes}
 \begin{tabular}{|l|l|}
 	\hline
-	Hanoi Towers (min steps)		& $T_n = 2^n - 1$\\
-	\#regions by $n$ lines			& $n\left(n + 1\right) / 2 + 1$\\
-	\#bounded regions by $n$ lines		& $\left(n^2 - 3n + 2\right) / 2$\\
-	\#labeled rooted trees			& $n^{n-1}$\\
-	\#labeled unrooted trees		& $n^{n-2}$\\
+	Türme von Hanoi, minimale Schirttzahl:					& $T_n = 2^n - 1$ \\
+	\#Regionen zwischen $n$ Gearden									& $n\left(n + 1\right) / 2 + 1$ \\
+	\#Abgeschlossene Regionen zwischen $n$ Geraden	& $\left(n^2 - 3n + 2\right) / 2$ \\
+	\#Markierte, gewurzelte Bäume										& $n^{n-1}$ \\
+	\#Markierte, nicht gewurzelte Bäume							& $n^{n-2}$ \\
 	\hline
 \end{tabular}
 
+\subsection{Satz von \textsc{Sprague-Grundy}}
+Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu:
+\[
+	g\left(X\right) := \min\left\{
+		\mathbb{Z}_0^+ \setminus
+		\left\{g\left(Y\right) \mid Y \text{ von } X \text{ aus direkt erreichbar}\right\}
+	\right\} 
+\]
+$X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\\\
+Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$.
+\lstinputlisting{math/nimm.cpp}
+
 \subsection{3D-Kugeln}
 \lstinputlisting{math/gcDist.cpp}
 
diff --git a/math/maxTeilfeld.cpp b/math/maxTeilfeld.cpp
index 2b732bb..bbafa3f 100644
--- a/math/maxTeilfeld.cpp
+++ b/math/maxTeilfeld.cpp
@@ -1,14 +1,15 @@
-//N :=  length of field
+// N := Länge des Feldes.
+// Laufzeit: O(N)
 int maxStart = 1, maxLen = 0, curStart = 1, len = 0;
 double maxValue = 0, sum = 0;
 for (int pos = 0; pos < N; pos++) {
 	sum += values[pos];
 	len++;
-	if (sum > maxValue) { // neues Maximum
+	if (sum > maxValue) { // Neues Maximum.
 		maxValue = sum; maxStart = curStart; maxLen = len;
 	}
-	if (sum < 0) { // alles zuruecksetzen
+	if (sum < 0) { // Alles zurücksetzen.
 		curStart = pos +2; len = 0; sum = 0;
 	}
 }
-//maxSum := maximaler Wert, maxStart := Startposition, maxLen := Laenge der Sequenz
\ No newline at end of file
+// maxSum := maximaler Wert, maxStart := Startposition, maxLen := Länge der Sequenz
diff --git a/math/modExp.cpp b/math/modExp.cpp
index 863ff4e..cd0f982 100644
--- a/math/modExp.cpp
+++ b/math/modExp.cpp
@@ -1,4 +1,4 @@
-//0<=a,b <=n and n <= MAX(ll)/2
+// Laufzeit: O(log(b))
 ll mult_mod(ll a, ll b, ll n) {
 	if(a == 0 || b == 0) return 0;
 	if(b == 1) return a % n;
@@ -7,7 +7,7 @@ ll mult_mod(ll a, ll b, ll n) {
 	else return mult_mod((a + a) % n, b / 2, n);
 }
 
-//0<=a,b<=n and n <= MAX(ll)/2
+// Laufzeit: O(log(b))
 ll pow_mod(ll a, ll b, ll n) {
 	if(b == 0) return 1;
 	if(b == 1) return a % n;
diff --git a/math/multInv.cpp b/math/multInv.cpp
index f9db815..858e47c 100644
--- a/math/multInv.cpp
+++ b/math/multInv.cpp
@@ -1,5 +1,6 @@
-ll multInv(ll n, ll p) { //berechnet das multiplikative Inverse von n in F_p
-	extendedEuclid(n, p); //implementierung von oben
+// Laufzeit: O(log (n) + log(p))
+ll multInv(ll n, ll p) { // Berechnet das multiplikative Inverse von n in F_p.
+	extendedEuclid(n, p); // Implementierung von oben.
 	x += ((x / p) + 1) * p;
 	return x % p;
-}
\ No newline at end of file
+}
diff --git a/math/nimm.cpp b/math/nimm.cpp
index 837a2ad..0b2d0c0 100644
--- a/math/nimm.cpp
+++ b/math/nimm.cpp
@@ -1,4 +1,4 @@
-#Most important function!!!11elf
+// Laufzeit: O(#game)
 bool WinNimm(vector<int> game) {
 	int result = 0;
 	for(int s: game) result ^= s;
diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp
index 4732d0a..5e8d6f8 100644
--- a/math/primeSieve.cpp
+++ b/math/primeSieve.cpp
@@ -1,4 +1,4 @@
-// Sieb des Eratosthenes. Laufzeit: O(n * log log n)
+// Laufzeit: O(n * log log n)
 #define N 100000001 // Bis 10^8 in unter 64MB Speicher.
 bitset<N / 2> isPrime;