From ef95a81b809ec6fcaf53a870f7bc86bf613b42f8 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Tue, 30 Jul 2024 15:57:54 +0200
Subject: removed old slow code

---
 content/math/math.tex | 2 --
 1 file changed, 2 deletions(-)

(limited to 'content/math/math.tex')

diff --git a/content/math/math.tex b/content/math/math.tex
index f99d0d4..c15825f 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -109,8 +109,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/millerRabin.cpp}
 	\method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}4]{n}}
 	\sourcecode{math/rho.cpp}
-	%\method{squfof}{findet zufälligen Teiler}{\sqrt[\leftroot{4}\uproot{2}4]{n}}
-	%\sourcecode{math/squfof.cpp}
 \end{algorithm}
 
 \begin{algorithm}{Teiler}
-- 
cgit v1.2.3


From 9e9c033aa41f786f494cadea43563f83f3e951a3 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Sat, 7 Sep 2024 23:41:49 +0200
Subject: insert divsum

---
 content/graph/dinicScaling.cpp |  21 +++++++++++++--------
 content/graph/graph.tex        |   4 ++--
 content/math/divSum.cpp        |  15 +++++++--------
 content/math/gauss.cpp         |  12 +++++-------
 content/math/lgsFp.cpp         |   3 +--
 content/math/math.tex          |  14 ++++++++++----
 content/tcr.tex                |   1 -
 tcr.pdf                        | Bin 673187 -> 691497 bytes
 8 files changed, 38 insertions(+), 32 deletions(-)

(limited to 'content/math/math.tex')

diff --git a/content/graph/dinicScaling.cpp b/content/graph/dinicScaling.cpp
index f4e833a..0974b78 100644
--- a/content/graph/dinicScaling.cpp
+++ b/content/graph/dinicScaling.cpp
@@ -26,17 +26,18 @@ bool bfs(ll lim) {
 	return dist[t] >= 0;
 }
 
-bool dfs(int v, ll flow) {
-	if (v == t) return true;
+ll dfs(int v, ll flow) {
+	if (v == t || flow == 0) return flow;
 	for (; pt[v] < sz(adj[v]); pt[v]++) {
 		Edge& e = adj[v][pt[v]];
 		if (dist[e.to] != dist[v] + 1) continue;
-		if (e.c - e.f >= flow && dfs(e.to, flow)) {
-			e.f += flow;
-			adj[e.to][e.rev].f -= flow;
-			return true;
+		ll cur = dfs(e.to, min(e.c - e.f, flow));
+		if (cur > 0) {
+			e.f += cur;
+			adj[e.to][e.rev].f -= cur;
+			return cur;
 	}}
-	return false;
+	return 0;
 }
 
 ll maxFlow(int source, int target) {
@@ -45,7 +46,11 @@ ll maxFlow(int source, int target) {
 	for (ll lim = (1LL << 62); lim >= 1; lim /= 2) {
 		while (bfs(lim)) {
 			pt.assign(sz(adj), 0);
-			while (dfs(s, lim)) flow += lim;
+			ll cur;
+			do {
+				cur = dfs(s, lim);
+				flow += cur;
+			} while (cur > 0);
 	}}
 	return flow;
 }
diff --git a/content/graph/graph.tex b/content/graph/graph.tex
index 831f4e5..213c597 100644
--- a/content/graph/graph.tex
+++ b/content/graph/graph.tex
@@ -211,6 +211,8 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\end{methods}
 	\sourcecode{graph/minCostMaxFlow.cpp}
 \end{algorithm}
+\vfill\null
+\columnbreak
 
 \subsubsection{Dinic's Algorithm mit Capacity Scaling}
 \begin{methods}
@@ -218,8 +220,6 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1}
 \end{methods}
 \sourcecode{graph/dinicScaling.cpp}
-\vfill\null
-\columnbreak
 
 \optional{
 \subsubsection{Anwendungen}
diff --git a/content/math/divSum.cpp b/content/math/divSum.cpp
index dc4bc4d..48302b5 100644
--- a/content/math/divSum.cpp
+++ b/content/math/divSum.cpp
@@ -1,9 +1,8 @@
-// Calculates the sum of (a*i+b)/m for i=0..(n-1) in O(log(n))
-// Note that b should not be negative!
 ll divSum(ll n, ll m, ll a, ll b){
-	if(m == 0) return 0;
-	ll ans = a/m * n*(n-1) / 2 + b/m * n;
-	a %= m, b %= m;
-	ll y = (a*(n-1)+b)/m;
-	return ans + y*(n-1) - divSum(y, a, m, m-b-1);
-}
\ No newline at end of file
+	if (m == 0) return 0;
+	ll ans = a/m * n*(n-1)/2 + b/m * n;
+	a %= m;
+	b %= m;
+	ll y = (a*(n-1)+b) / m;
+	return ans + y * (n-1) - divSum(y, a, m, m-b-1);
+}
diff --git a/content/math/gauss.cpp b/content/math/gauss.cpp
index 8129fd2..d431e52 100644
--- a/content/math/gauss.cpp
+++ b/content/math/gauss.cpp
@@ -14,19 +14,17 @@ void takeAll(int n, int line) {
 int gauss(int n) {
 	vector<bool> done(n, false);
 	for (int i = 0; i < n; i++) {
-		int swappee = i; // Sucht Pivotzeile für bessere Stabilität.
-		for (int j = 0; j < n; j++) {
-			if (done[j]) continue;
-			if (abs(mat[j][i]) > abs(mat[i][i])) swappee = j;
+		int j = i; // Sucht Pivotzeile für bessere Stabilität.
+		for (int k = 0; k < n; k++) {
+			if (!done[k] && abs(mat[k][i]) > abs(mat[i][i])) j = k;
 		}
-		swap(mat[i], mat[swappee]);
+		swap(mat[i], mat[j]);
 		if (abs(mat[i][i]) > EPS) {
 			normalLine(i);
 			takeAll(n, i);
 			done[i] = true;	
 	}}
-	// Ab jetzt nur checks bzgl. Eindeutigkeit/Existenz der Lösung.
-	for (int i = 0; i < n; i++) {
+	for (int i = 0; i < n; i++) { // gauss fertig, prüfe Lösung
 		bool allZero = true;
 		for (int j = i; j < n; j++) allZero &= abs(mat[i][j]) <= EPS;
 		if (allZero && abs(mat[i][n]) > EPS) return INCONSISTENT;
diff --git a/content/math/lgsFp.cpp b/content/math/lgsFp.cpp
index 0241742..bf18c86 100644
--- a/content/math/lgsFp.cpp
+++ b/content/math/lgsFp.cpp
@@ -22,5 +22,4 @@ void gauss(int n, ll mod) {
 		normalLine(i, mod);
 		takeAll(n, i, mod);
 		done[i] = true;
-}}
-// für Eindeutigkeit, Existenz etc. siehe LGS über R @\sourceref{math/gauss.cpp}@
+}} // für Eindeutigkeit, Existenz etc. siehe LGS über R @\sourceref{math/gauss.cpp}@
diff --git a/content/math/math.tex b/content/math/math.tex
index c15825f..fffdf37 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -306,7 +306,10 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 \method{gauss}{löst LGS}{n^3}
 \sourcecode{math/gauss.cpp}
 
-\vfill\null\columnbreak
+\begin{algorithm}{Inversionszahl}
+	\vspace{-2pt}
+	\sourcecode{math/inversions.cpp}
+\end{algorithm}
 
 \begin{algorithm}{Numerisch Extremstelle bestimmen}
 	\sourcecode{math/goldenSectionSearch.cpp}
@@ -316,7 +319,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/simpson.cpp}
 \end{algorithm}
 
-
 \begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}
 	Multipliziert Polynome $A$ und $B$.
 	\begin{itemize}
@@ -340,8 +342,11 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
     \sourcecode{math/transforms/seriesOperations.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Inversionszahl}
-	\sourcecode{math/inversions.cpp}
+
+\begin{algorithm}{Div Sum}
+	\method{divSum}{berechnet $\sum_{i=0}^{n-1} \frac{a\cdot i + b}{m}$}{\log(n)}
+	\textbf{Wichtig:} $b$ darf nicht negativ sein!
+	\sourcecode{math/divSum.cpp}
 \end{algorithm}
 
 \subsection{Satz von \textsc{Sprague-Grundy}}
@@ -394,6 +399,7 @@ so gilt
 	\end{methods}
 	\sourcecode{math/binomial0.cpp}
 	Falls $n >= p$ for $\mathit{mod}=p^k$ berechne \textit{fac} und \textit{inv} aber teile $p$ aus $i$ und berechne die häufigkeit von $p$ in $n!$ als $\sum\limits_{i=1}\big\lfloor\frac{n}{p^i}\big\rfloor$
+	\columnbreak
 
     \begin{methods}
 		\method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k}
diff --git a/content/tcr.tex b/content/tcr.tex
index 4e4353b..b3cfb17 100644
--- a/content/tcr.tex
+++ b/content/tcr.tex
@@ -17,7 +17,6 @@
 \usepackage[T1]{fontenc}
 \usepackage[ngerman]{babel}
 \usepackage[utf8]{inputenc}
-\usepackage[nopatch=footnote]{microtype}
 \usepackage[hidelinks,pdfencoding=auto]{hyperref}
 
 % Include headers.
diff --git a/tcr.pdf b/tcr.pdf
index 488ac70..c16c3cc 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3


From df963645ca0c5d0bed4fb9c02e93233dcfd53dae Mon Sep 17 00:00:00 2001
From: Lucas Schwebler <lucas.schwebler@gmail.com>
Date: Sun, 8 Sep 2024 14:57:14 +0200
Subject: add min mod (mimumum of linear function modulo m)

---
 content/math/math.tex   |   9 ++++-
 content/math/minMod.cpp |  18 ++++++++++
 tcr.pdf                 | Bin 691497 -> 693864 bytes
 test/math/minMod.cpp    |  92 ++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 118 insertions(+), 1 deletion(-)
 create mode 100644 content/math/minMod.cpp
 create mode 100644 test/math/minMod.cpp

(limited to 'content/math/math.tex')

diff --git a/content/math/math.tex b/content/math/math.tex
index fffdf37..6b765ca 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -344,11 +344,18 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 
 
 \begin{algorithm}{Div Sum}
-	\method{divSum}{berechnet $\sum_{i=0}^{n-1} \frac{a\cdot i + b}{m}$}{\log(n)}
+	\method{divSum}{berechnet $\sum_{i=0}^{n-1} \left\lfloor \frac{a\cdot i + b}{m}  \right\rfloor$}{\log(n)}
 	\textbf{Wichtig:} $b$ darf nicht negativ sein!
 	\sourcecode{math/divSum.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Min Mod}
+	\method{firstVal}{berechnet den ersten Wert von $0,\ a, \ldots,\ a \cdot i \bmod{m}$, der in $[l, r]$ liegt. Gibt $-1$ zurück, falls er nicht existiert.}{\log(m)}
+	\method{minMod}{berechnet das Minimum von $(a \cdot i + b) \bmod{m}$ für $i \in [0, n)$}{\log(m)}
+	\textbf{Wichtig:} $0 \leq a, b, l, r < m$
+	\sourcecode{math/minMod.cpp}
+\end{algorithm}
+
 \subsection{Satz von \textsc{Sprague-Grundy}}
 Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu:
 \[
diff --git a/content/math/minMod.cpp b/content/math/minMod.cpp
new file mode 100644
index 0000000..2db060a
--- /dev/null
+++ b/content/math/minMod.cpp
@@ -0,0 +1,18 @@
+ll firstVal(ll a, ll m, ll l, ll r){
+	if(l == 0) return 0;
+	if(a == 0) return -1;
+	if((l-1)/a < r/a) return (l+a-1)/a*a;
+	ll s = (r+a-1)/a*a;
+	ll v = firstVal(m%a, a, s-r, s-l);
+	return v == -1 ? -1 : s - v;
+}
+
+ll minMod(ll n, ll m, ll a, ll b){
+	if(a == 0) return b;
+	ll g = gcd(m, a), c = b%g;
+	m /= g, a /= g, b /= g;
+	ll ai = multInv(a, m);
+	ll l = ai*b % m, r = (n-1 + ai*b) % m;
+	if(n >= m || l > r) return c;
+	return a * firstVal(ai, m, l, r) % m * g + c;
+}
\ No newline at end of file
diff --git a/tcr.pdf b/tcr.pdf
index c16c3cc..7dc830e 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/test/math/minMod.cpp b/test/math/minMod.cpp
new file mode 100644
index 0000000..e49da11
--- /dev/null
+++ b/test/math/minMod.cpp
@@ -0,0 +1,92 @@
+#include "../util.h"
+#include <math/shortModInv.cpp>
+#include <math/minMod.cpp>
+
+ll naiveMinMod(ll n, ll m, ll a, ll b){
+	ll ans = m;
+	for(ll i = 0; i < n; i++){
+		ans = min(ans, (a*i+b)%m);
+	}
+	return ans;
+}
+
+ll naiveFirstVal(ll a, ll m, ll l, ll r){
+	for(ll i = 0; i < m; i++){
+		ll v = a*i % m;
+		if(l <= v && v <= r) return v;
+	}
+	return -1;
+}
+
+void stress_test_minMod() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 100);
+		int m = Random::integer<int>(1, 100);
+		int a = Random::integer<int>(0, m);
+		int b = Random::integer<int>(0, m);
+		ll expected = naiveMinMod(n, m, a, b);
+		ll got = minMod(n, m, a, b);
+		if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		queries++;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+void stress_test_firstVal() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int m = Random::integer<int>(1, 100);
+		int a = Random::integer<int>(0, m);
+		int l = Random::integer<int>(0, m);
+		int r = Random::integer<int>(0, m);
+		if(l > r) swap(l, r);
+		ll expected = naiveFirstVal(a, m, l, r);
+		ll got = firstVal(a, m, l, r);
+		if (got != expected) cerr << a << " " << m << " " << l << " " << r << "got: " << got << ", expected: " << expected << FAIL;
+		queries++;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test_minMod() {
+	timer t;
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll n = Random::integer<ll>(1, 1'000'000'000);
+		ll m = Random::integer<ll>(1, 1'000'000'000);
+		ll a = Random::integer<ll>(0, m);
+		ll b = Random::integer<ll>(0, m);
+		t.start();
+		hash += minMod(n, m, a, b);
+		t.stop();
+	}
+	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+void performance_test_firstVal() {
+	timer t;
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll m = Random::integer<ll>(1, 1'000'000'000);
+		ll a = Random::integer<ll>(1, m);
+		ll l = Random::integer<ll>(0, m);
+		ll r = Random::integer<ll>(0, m);
+		if(l > r) swap(l, r);
+		t.start();
+		hash += firstVal(a, m, l, r);
+		t.stop();
+	}
+	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test_minMod();
+	stress_test_firstVal();
+	performance_test_minMod();
+	performance_test_firstVal();
+}
+
-- 
cgit v1.2.3


From 45d95c45013bf4ff73570c94c58b7f0212ccdf26 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Sun, 8 Sep 2024 22:16:36 +0200
Subject: moved stuff

---
 content/math/math.tex               |  79 ++++++++++++++++++++++++------------
 content/math/minMod.cpp             |  26 +++++++-----
 content/math/tables.tex             |  18 --------
 content/math/tables/binom.tex       |  31 +++++++-------
 content/math/tables/composite.tex   |  45 ++++++++++----------
 content/math/tables/nim.tex         |   5 ++-
 content/math/tables/numbers.tex     |  59 ---------------------------
 content/math/tables/platonic.tex    |  26 ++++++------
 content/math/tables/probability.tex |  17 ++++----
 content/math/tables/series.tex      |  32 +++++++--------
 content/math/tables/stuff.tex       |   9 ++--
 content/tcr.tex                     |   3 --
 tcr.pdf                             | Bin 693864 -> 696377 bytes
 13 files changed, 148 insertions(+), 202 deletions(-)
 delete mode 100644 content/math/tables.tex
 delete mode 100644 content/math/tables/numbers.tex

(limited to 'content/math/math.tex')

diff --git a/content/math/math.tex b/content/math/math.tex
index 6b765ca..c07a41e 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -342,31 +342,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
     \sourcecode{math/transforms/seriesOperations.cpp}
 \end{algorithm}
 
-
-\begin{algorithm}{Div Sum}
-	\method{divSum}{berechnet $\sum_{i=0}^{n-1} \left\lfloor \frac{a\cdot i + b}{m}  \right\rfloor$}{\log(n)}
-	\textbf{Wichtig:} $b$ darf nicht negativ sein!
-	\sourcecode{math/divSum.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Min Mod}
-	\method{firstVal}{berechnet den ersten Wert von $0,\ a, \ldots,\ a \cdot i \bmod{m}$, der in $[l, r]$ liegt. Gibt $-1$ zurück, falls er nicht existiert.}{\log(m)}
-	\method{minMod}{berechnet das Minimum von $(a \cdot i + b) \bmod{m}$ für $i \in [0, n)$}{\log(m)}
-	\textbf{Wichtig:} $0 \leq a, b, l, r < m$
-	\sourcecode{math/minMod.cpp}
-\end{algorithm}
-
-\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)$.
-
 \subsection{Kombinatorik}
 
 \paragraph{Wilsons Theorem}
@@ -400,13 +375,14 @@ so gilt
 \paragraph{Binomialkoeffizienten}
 	Die Anzahl der \mbox{$k$-elementigen} Teilmengen einer \mbox{$n$-elementigen} Menge.
 	
+	\input{math/tables/binom}
+	
 	\begin{methods}
 		\method{precalc}{berechnet $n!$ und $n!^{-1}$ vor}{\mathit{lim}}
 		\method{calc\_binom}{berechnet Binomialkoeffizient}{1}
 	\end{methods}
 	\sourcecode{math/binomial0.cpp}
 	Falls $n >= p$ for $\mathit{mod}=p^k$ berechne \textit{fac} und \textit{inv} aber teile $p$ aus $i$ und berechne die häufigkeit von $p$ in $n!$ als $\sum\limits_{i=1}\big\lfloor\frac{n}{p^i}\big\rfloor$
-	\columnbreak
 
     \begin{methods}
 		\method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k}
@@ -519,6 +495,54 @@ Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$.
 \subsection{The Twelvefold Way \textnormal{(verteile $n$ Bälle auf $k$ Boxen)}}
 \input{math/tables/twelvefold}
 
+\subsection{Platonische Körper}
+\input{math/tables/platonic}
+
+\input{math/tables/probability}
+
+\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)$.
+
+\subsection{Nim-Spiele}
+\begin{itemize}
+	\item[\ding{182}] letzter gewinnt (normal)
+	\item[\ding{183}] letzter verliert
+\end{itemize}
+\input{math/tables/nim}
+
+\subsection{Verschiedenes}
+\input{math/tables/stuff}
+
+\begin{algorithm}{Div Sum}
+	\method{divSum}{berechnet $\sum_{i=0}^{n-1} \left\lfloor \frac{a\cdot i + b}{m}  \right\rfloor$}{\log(n)}
+	\textbf{Wichtig:} $b$ darf nicht negativ sein!
+	\sourcecode{math/divSum.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Min Mod}
+	\begin{methods}
+		\method{firstVal}{berechnet den ersten Wert von $0,\ a, \ldots,\ a \cdot i \bmod{m}$,}{\log(m)}
+		\method{}{der in $[l, r]$ liegt. Gibt $-1$ zurück, falls er nicht existiert.}{}
+		\method{minMod}{berechnet das Minimum von $(a \cdot i + b) \bmod{m}$ für $i \in [0, n)$}{\log(m)}
+	\end{methods}
+	\textbf{Wichtig:} $0 \leq a, b, l, r < m$
+	\sourcecode{math/minMod.cpp}
+\end{algorithm}
+
+\subsection{Reihen}
+\input{math/tables/series}
+
+\subsection{Wichtige Zahlen}
+\input{math/tables/composite}
+
 \optional{
 \subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
 \begin{methods}
@@ -529,7 +553,8 @@ Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$.
 \sourcecode{math/piLehmer.cpp}
 }
 
-%\input{math/tables/numbers}
+\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
+\sourcecode{math/piLegendre.cpp}
 
 \begin{algorithm}[optional]{Big Integers}
 	\sourcecode{math/bigint.cpp}
diff --git a/content/math/minMod.cpp b/content/math/minMod.cpp
index 2db060a..91f31d0 100644
--- a/content/math/minMod.cpp
+++ b/content/math/minMod.cpp
@@ -1,18 +1,22 @@
-ll firstVal(ll a, ll m, ll l, ll r){
-	if(l == 0) return 0;
-	if(a == 0) return -1;
-	if((l-1)/a < r/a) return (l+a-1)/a*a;
-	ll s = (r+a-1)/a*a;
-	ll v = firstVal(m%a, a, s-r, s-l);
+ll firstVal(ll a, ll m, ll l, ll r) {
+	if (l == 0) return 0;
+	if (a == 0) return -1;
+	if ((l-1)/a < r/a) return (l+a-1) / a*a;
+	ll s = (r+a-1) / a*a;
+	ll v = firstVal(m % a, a, s-r, s-l);
 	return v == -1 ? -1 : s - v;
 }
 
-ll minMod(ll n, ll m, ll a, ll b){
-	if(a == 0) return b;
-	ll g = gcd(m, a), c = b%g;
-	m /= g, a /= g, b /= g;
+ll minMod(ll n, ll m, ll a, ll b) {
+	if (a == 0) return b;
+	ll g = gcd(m, a);
+	c = b%g;
+	m /= g;
+	a /= g;
+	b /= g;
 	ll ai = multInv(a, m);
-	ll l = ai*b % m, r = (n-1 + ai*b) % m;
+	ll l = ai*b % m;
+	ll r = (n-1 + ai*b) % m;
 	if(n >= m || l > r) return c;
 	return a * firstVal(ai, m, l, r) % m * g + c;
 }
\ No newline at end of file
diff --git a/content/math/tables.tex b/content/math/tables.tex
deleted file mode 100644
index 53f3758..0000000
--- a/content/math/tables.tex
+++ /dev/null
@@ -1,18 +0,0 @@
-\enlargethispage{0.2cm}
-\begin{multicols*}{2}
-	\input{math/tables/binom}
-	\vfill
-	\input{math/tables/composite}
-	\vfill
-	\input{math/tables/platonic}
-	\vfill
-	\input{math/tables/series}
-
-	\columnbreak
-
-	\input{math/tables/probability}
-	\vfill
-	\input{math/tables/stuff}
-	\vfill
-	\input{math/tables/nim}
-\end{multicols*}
diff --git a/content/math/tables/binom.tex b/content/math/tables/binom.tex
index 878a6b0..9fc9ae3 100644
--- a/content/math/tables/binom.tex
+++ b/content/math/tables/binom.tex
@@ -1,28 +1,27 @@
-\begin{tabularx}{\linewidth}{|XXXX|}
+\begin{expandtable}
+\begin{tabularx}{\linewidth}{|C|}
 	\hline
-	\multicolumn{4}{|c|}{Binomialkoeffizienten} \\
-	\hline
-	\multicolumn{4}{|c|}{
 	$\frac{n!}{k!(n - k)!} \hfill=\hfill
 	\binom{n}{k} \hfill=\hfill
 	\binom{n}{n - k} \hfill=\hfill
 	\frac{n}{k}\binom{n - 1}{k - 1} \hfill=\hfill
 	\frac{n-k+1}{k}\binom{n}{k - 1} \hfill=\hfill
-	\binom{n - 1}{k} + \binom{n - 1}{k - 1} \hfill=\hfill
+	\frac{k+1}{n-k}\binom{n}{k + 1} \hfill=\hfill$\\
+	
+	$\binom{n - 1}{k - 1} + \binom{n - 1}{k} \hfill=\hfill
+	\binom{n + 1}{k + 1} - \binom{n}{k + 1} \hfill=\hfill
 	(-1)^k \binom{k - n - 1}{k} \hfill\approx\hfill
-	2^{n} \cdot \frac{2}{\sqrt{2\pi n}}\cdot\exp\left(-\frac{2(x - \frac{n}{2})^2}{n}\right)$
-	} \\
+	2^{n} \cdot \frac{2}{\sqrt{2\pi n}}\cdot\exp\left(-\frac{2(x - \frac{n}{2})^2}{n}\right)$\\
 	\grayhline
 	
-	$\sum\limits_{k = 0}^n \binom{n}{k} = 2^n$ &
-	$\sum\limits_{k = 0}^n \binom{k}{m} = \binom{n + 1}{m + 1}$ &
-	$\sum\limits_{i = 0}^n \binom{n}{i}^2 = \binom{2n}{n}$ &
-	$\sum\limits_{k = 0}^n\binom{r + k}{k} = \binom{r + n + 1}{n}$\\
+	$\sum\limits_{k = 0}^n \binom{n}{k} = 2^n\hfill
+	\sum\limits_{k = 0}^n \binom{k}{m} = \binom{n + 1}{m + 1}\hfill
+	\sum\limits_{i = 0}^n \binom{n}{i}^2 = \binom{2n}{n}\hfill
+	\sum\limits_{k = 0}^n\binom{r + k}{k} = \binom{r + n + 1}{n}$\\
 	
-	$\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n - k}{m - k}$ &
-	$\sum\limits_{k = 0}^n \binom{r}{k}\binom{s}{n - k} = \binom{r + s}{n}$ &
-	\multicolumn{2}{l|}{
-	$\sum\limits_{i = 1}^n \binom{n}{i} F_i = F_{2n} \quad F_n = n\text{-th Fib.}$
-	}\\
+	$\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n - k}{m - k}\hfill
+	\sum\limits_{k = 0}^n \binom{r}{k}\binom{s}{n - k} = \binom{r + s}{n}\hfill
+	\sum\limits_{i = 1}^n \binom{n}{i} \mathit{Fib}_i = \mathit{Fib}_{2n}$\\
 	\hline
 \end{tabularx}
+\end{expandtable}
diff --git a/content/math/tables/composite.tex b/content/math/tables/composite.tex
index c261db1..7a6ab09 100644
--- a/content/math/tables/composite.tex
+++ b/content/math/tables/composite.tex
@@ -1,27 +1,26 @@
-
-\begin{tabularx}{\linewidth}{|r||r||r|r||r|r|r||C|}
+\begin{expandtable}
+\begin{tabularx}{\linewidth}{|r||r|R||r||r|}
 	\hline
-	\multicolumn{8}{|c|}{Important Numbers} \\
+	$10^x$ &             Highly Composite &  \# Divs & \# prime Divs &                   \# Primes \\
 	\hline
-	$10^x$ &             Highly Composite &  \# Divs & $<$ Prime & $>$ Prime &                   \# Primes & primorial & \\
-	\hline
-	     1 &                            6 &        4 &      $-3$ &      $+1$ &                           4 &         2 & \\
-	     2 &                           60 &       12 &      $-3$ &      $+1$ &                          25 &         3 & \\
-	     3 &                          840 &       32 &      $-3$ &      $+9$ &                         168 &         4 & \\
-	     4 &                       7\,560 &       64 &     $-27$ &      $+7$ &                      1\,229 &         5 & \\
-	     5 &                      83\,160 &      128 &      $-9$ &      $+3$ &                      9\,592 &         6 & \\
-	     6 &                     720\,720 &      240 &     $-17$ &      $+3$ &                     78\,498 &         7 & \\
-	     7 &                  8\,648\,640 &      448 &      $-9$ &     $+19$ &                    664\,579 &         8 & \\
-	     8 &                 73\,513\,440 &      768 &     $-11$ &      $+7$ &                 5\,761\,455 &         8 & \\
-	     9 &                735\,134\,400 &   1\,344 &     $-63$ &      $+7$ &                50\,847\,534 &         9 & \\
-	    10 &             6\,983\,776\,800 &   2\,304 &     $-33$ &     $+19$ &               455\,052\,511 &        10 & \\
-	    11 &            97\,772\,875\,200 &   4\,032 &     $-23$ &      $+3$ &            4\,118\,054\,813 &        10 & \\
-	    12 &           963\,761\,198\,400 &   6\,720 &     $-11$ &     $+39$ &           37\,607\,912\,018 &        11 & \\
-	    13 &        9\,316\,358\,251\,200 &  10\,752 &     $-29$ &     $+37$ &          346\,065\,536\,839 &        12 & \\
-	    14 &       97\,821\,761\,637\,600 &  17\,280 &     $-27$ &     $+31$ &       3\,204\,941\,750\,802 &        12 & \\
-	    15 &      866\,421\,317\,361\,600 &  26\,880 &     $-11$ &     $+37$ &      29\,844\,570\,422\,669 &        13 & \\
-	    16 &   8\,086\,598\,962\,041\,600 &  41\,472 &     $-63$ &     $+61$ &     279\,238\,341\,033\,925 &        13 & \\
-	    17 &  74\,801\,040\,398\,884\,800 &  64\,512 &      $-3$ &      $+3$ &  2\,623\,557\,157\,654\,233 &        14 & \\
-	    18 & 897\,612\,484\,786\,617\,600 & 103\,680 &     $-11$ &      $+3$ & 24\,739\,954\,287\,740\,860 &        16 & \\
+	     1 &                            6 &        4 &             2 &                           4 \\
+	     2 &                           60 &       12 &             3 &                          25 \\
+	     3 &                          840 &       32 &             4 &                         168 \\
+	     4 &                       7\,560 &       64 &             5 &                      1\,229 \\
+	     5 &                      83\,160 &      128 &             6 &                      9\,592 \\
+	     6 &                     720\,720 &      240 &             7 &                     78\,498 \\
+	     7 &                  8\,648\,640 &      448 &             8 &                    664\,579 \\
+	     8 &                 73\,513\,440 &      768 &             8 &                 5\,761\,455 \\
+	     9 &                735\,134\,400 &   1\,344 &             9 &                50\,847\,534 \\
+	    10 &             6\,983\,776\,800 &   2\,304 &            10 &               455\,052\,511 \\
+	    11 &            97\,772\,875\,200 &   4\,032 &            10 &            4\,118\,054\,813 \\
+	    12 &           963\,761\,198\,400 &   6\,720 &            11 &           37\,607\,912\,018 \\
+	    13 &        9\,316\,358\,251\,200 &  10\,752 &            12 &          346\,065\,536\,839 \\
+	    14 &       97\,821\,761\,637\,600 &  17\,280 &            12 &       3\,204\,941\,750\,802 \\
+	    15 &      866\,421\,317\,361\,600 &  26\,880 &            13 &      29\,844\,570\,422\,669 \\
+	    16 &   8\,086\,598\,962\,041\,600 &  41\,472 &            13 &     279\,238\,341\,033\,925 \\
+	    17 &  74\,801\,040\,398\,884\,800 &  64\,512 &            14 &  2\,623\,557\,157\,654\,233 \\
+	    18 & 897\,612\,484\,786\,617\,600 & 103\,680 &            16 & 24\,739\,954\,287\,740\,860 \\
 	\hline
 \end{tabularx}
+\end{expandtable}
diff --git a/content/math/tables/nim.tex b/content/math/tables/nim.tex
index 8490d42..66e289e 100644
--- a/content/math/tables/nim.tex
+++ b/content/math/tables/nim.tex
@@ -1,6 +1,5 @@
+\begin{expandtable}
 \begin{tabularx}{\linewidth}{|p{0.37\linewidth}|X|}
-	\hline
-	\multicolumn{2}{|c|}{Nim-Spiele (\ding{182} letzter gewinnt (normal), \ding{183} letzter verliert)} \\
 	\hline
 	Beschreibung &
 	Strategie \\
@@ -94,3 +93,5 @@
 	Periode ab $n = 72$ der Länge $12$.\\
 	\hline
 \end{tabularx}
+\end{expandtable}
+	
\ No newline at end of file
diff --git a/content/math/tables/numbers.tex b/content/math/tables/numbers.tex
deleted file mode 100644
index 1dc9f38..0000000
--- a/content/math/tables/numbers.tex
+++ /dev/null
@@ -1,59 +0,0 @@
-\begin{expandtable}
-\begin{tabularx}{\linewidth}{|l|X|}
-	\hline
-	\multicolumn{2}{|c|}{Berühmte Zahlen} \\
-	\hline
-	\textsc{Fibonacci}	&
-	$f(0) = 0 \quad
-	f(1) = 1 \quad
-	f(n+2) = f(n+1) + f(n)$ \\
-	\grayhline
-	
-	\textsc{Catalan}	&
-	$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}$ \\
-	\grayhline
-	
-	\textsc{Euler} I &
-	$\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \qquad
-	\eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1} $ \\
-	\grayhline
-	
-	\textsc{Euler} II &
-	$\eulerII{n}{0} = 1 \quad
-	\eulerII{n}{n} = 0 \quad$\\
-	& $\eulerII{n}{k} = (k+1) \eulerII{n-1}{k} + (2n-k-1) \eulerII{n-1}{k-1}$ \\
-	\grayhline
-	
-	\textsc{Stirling} I &
-	$\stirlingI{0}{0} = 1 \qquad
-	\stirlingI{n}{0} = \stirlingI{0}{n} = 0 \qquad
-	\stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}$ \\
-	\grayhline
-	
-	\textsc{Stirling} II &
-	$\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad
-	\stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1} =
-	\frac{1}{k!} \sum\limits_{j=0}^{k} (-1)^{k-j}\binom{k}{j}j^n$\\
-	\grayhline
-	
-	\textsc{Bell} &
-	$B_1 = 1 \qquad
-	B_n = \sum\limits_{k = 0}^{n - 1} B_k\binom{n-1}{k}
-	= \sum\limits_{k = 0}^{n}\stirlingII{n}{k}$\\
-	\grayhline
-	
-	\textsc{Partitions} &
-	$p(0,0) = 1 \quad
-	p(n,k) = 0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0$ \\
-	& $p(n,k) = p(n-k,k) + p(n-1,k-1)$\\
-	\grayhline
-	
-	\textsc{Partitions} &
-	$f(0) = 1 \quad f(n) = 0~(n < 0)$ \\
-	& $f(n)=\sum\limits_{k=1}^\infty(-1)^{k-1}f(n - \frac{k(3k+1)}{2})+\sum\limits_{k=1}^\infty(-1)^{k-1}f(n - \frac{k(3k-1)}{2})$\\
-	
-	\hline
-\end{tabularx}
-\end{expandtable}
diff --git a/content/math/tables/platonic.tex b/content/math/tables/platonic.tex
index f4ee554..2866ccf 100644
--- a/content/math/tables/platonic.tex
+++ b/content/math/tables/platonic.tex
@@ -1,39 +1,39 @@
+\begin{expandtable}
 \begin{tabularx}{\linewidth}{|X|CCCX|}
 	\hline
-	\multicolumn{5}{|c|}{Platonische Körper} \\
-	\hline
-	Übersicht       & Seiten & Ecken & Kanten & dual zu \\
+	Übersicht       & |F|    & |V|   & |E|    & dual zu \\
 	\hline
 	Tetraeder       & 4      & 4     & 6      & Tetraeder \\
-	Würfel/Hexaeder & 6      & 8     & 12     & Oktaeder \\
-	Oktaeder        & 8      & 6     & 12     & Würfel/Hexaeder\\
+	Würfel          & 6      & 8     & 12     & Oktaeder \\
+	Oktaeder        & 8      & 6     & 12     & Würfel\\
 	Dodekaeder      & 12     & 20    & 30     & Ikosaeder \\
 	Ikosaeder       & 20     & 12    & 30     & Dodekaeder \\
 	\hline
 	\multicolumn{5}{|c|}{Färbungen mit maximal $n$ Farben (bis auf Isomorphie)} \\
 	\hline
-	\multicolumn{3}{|l}{Ecken vom Oktaeder/Seiten vom Würfel} &
+	\multicolumn{3}{|l}{|V| vom Oktaeder/|F| vom Würfel} &
 	\multicolumn{2}{l|}{$(n^6 + 3n^4 + 12n^3 + 8n^2)/24$} \\
 
-	\multicolumn{3}{|l}{Ecken vom Würfel/Seiten vom Oktaeder} &
+	\multicolumn{3}{|l}{|V| vom Würfel/|F| vom Oktaeder} &
 	\multicolumn{2}{l|}{$(n^8 + 17n^4 + 6n^2)/24$} \\
 
-	\multicolumn{3}{|l}{Kanten vom Würfel/Oktaeder} &
+	\multicolumn{3}{|l}{|E| vom Würfel/Oktaeder} &
 	\multicolumn{2}{l|}{$(n^{12} + 6n^7 + 3n^6 + 8n^4 + 6n^3)/24$} \\
 
-	\multicolumn{3}{|l}{Ecken/Seiten vom Tetraeder} &
+	\multicolumn{3}{|l}{|V|/|F| vom Tetraeder} &
 	\multicolumn{2}{l|}{$(n^4 + 11n^2)/12$} \\
 
-	\multicolumn{3}{|l}{Kanten vom Tetraeder} &
+	\multicolumn{3}{|l}{|E| vom Tetraeder} &
 	\multicolumn{2}{l|}{$(n^6 + 3n^4 + 8n^2)/12$} \\
 
-	\multicolumn{3}{|l}{Ecken vom Ikosaeder/Seiten vom Dodekaeder} &
+	\multicolumn{3}{|l}{|V| vom Ikosaeder/|F| vom Dodekaeder} &
 	\multicolumn{2}{l|}{$(n^{12} + 15n^6 + 44n^4)/60$} \\
 
-	\multicolumn{3}{|l}{Ecken vom Dodekaeder/Seiten vom Ikosaeder} &
+	\multicolumn{3}{|l}{|V| vom Dodekaeder/|F| vom Ikosaeder} &
 	\multicolumn{2}{l|}{$(n^{20} + 15n^{10} + 20n^8 + 24n^4)/60$} \\
 
-	\multicolumn{3}{|l}{Kanten vom Dodekaeder/Ikosaeder (evtl. falsch)} &
+	\multicolumn{3}{|l}{|E| vom Dodekaeder/Ikosaeder} &
 	\multicolumn{2}{l|}{$(n^{30} + 15n^{16} + 20n^{10} + 24n^6)/60$} \\
 	\hline
 \end{tabularx}
+\end{expandtable}
diff --git a/content/math/tables/probability.tex b/content/math/tables/probability.tex
index f265d10..29f92e1 100644
--- a/content/math/tables/probability.tex
+++ b/content/math/tables/probability.tex
@@ -1,19 +1,15 @@
-\begin{tabularx}{\linewidth}{|LICIR|}
+\begin{expandtable}
+\begin{tabularx}{\linewidth}{|LIR|}
 	\hline
-	\multicolumn{3}{|c|}{
+	\multicolumn{2}{|c|}{
 		Wahrscheinlichkeitstheorie ($A,B$ Ereignisse und $X,Y$ Variablen)
 	} \\
 	\hline
-	$\E(X + Y) = \E(X) + \E(Y)$ &
-	$\E(\alpha X) = \alpha \E(X)$ &
-	$X, Y$ unabh. $\Leftrightarrow \E(XY) = \E(X) \cdot \E(Y)$\\
-	
-	$\Pr[A \vert B] = \frac{\Pr[A \land B]}{\Pr[B]}$ &
-	$A, B$ disj. $\Leftrightarrow \Pr[A \land B] = \Pr[A] \cdot \Pr[B]$ &
-	$\Pr[A \lor B] = \Pr[A] + \Pr[B] - \Pr[A \land B]$ \\
+	$\E(X + Y) = \E(X) + \E(Y)$                                & $\Pr[A \vert B] = \frac{\Pr[A \land B]}{\Pr[B]}$ \\
+	$\E(\alpha X) = \alpha \E(X)$                              & $\Pr[A \lor B] = \Pr[A] + \Pr[B] - \Pr[A \land B]$ \\
+	$X, Y$ unabh. $\Leftrightarrow \E(XY) = \E(X) \cdot \E(Y)$ & $A, B$ disj. $\Leftrightarrow \Pr[A \land B] = \Pr[A] \cdot \Pr[B]$\\
 	\hline
 \end{tabularx}
-\vfill
 \begin{tabularx}{\linewidth}{|Xlr|lrX|}
 	\hline
 	\multicolumn{6}{|c|}{\textsc{Bertrand}'s Ballot Theorem (Kandidaten $A$ und $B$, $k \in \mathbb{N}$)} \\
@@ -25,3 +21,4 @@
 	$\#A \geq \#B + k$ & $Num = \frac{a - k + 1 - b}{a - k + 1} \binom{a + b - k}{b}$ & \\
 	\hline
 \end{tabularx}
+\end{expandtable}
diff --git a/content/math/tables/series.tex b/content/math/tables/series.tex
index 3042781..9618c2b 100644
--- a/content/math/tables/series.tex
+++ b/content/math/tables/series.tex
@@ -1,33 +1,33 @@
-\begin{tabularx}{\linewidth}{|XIXIXIX|}
-	\hline
-	\multicolumn{4}{|c|}{Reihen} \\
+\begin{expandtable}
+\begin{tabularx}{\linewidth}{|XIXIX|}
 	\hline
 	$\sum\limits_{i = 1}^n i = \frac{n(n+1)}{2}$ &
 	$\sum\limits_{i = 1}^n i^2 = \frac{n(n + 1)(2n + 1)}{6}$ &
-	$\sum\limits_{i = 1}^n i^3 = \frac{n^2 (n + 1)^2}{4}$ &
-	$H_n = \sum\limits_{i = 1}^n \frac{1}{i}$ \\
+	$\sum\limits_{i = 1}^n i^3 = \frac{n^2 (n + 1)^2}{4}$ \\
 	\grayhline
 	
-	$\sum\limits_{i = 0}^n c^i = \frac{c^{n + 1} - 1}{c - 1} \quad c \neq 1$ &	
-	$\sum\limits_{i = 0}^\infty c^i = \frac{1}{1 - c} \quad \vert c \vert < 1$ &
-	$\sum\limits_{i = 1}^\infty c^i = \frac{c}{1 - c} \quad \vert c \vert < 1$ &	
-	$\sum\limits_{i = 0}^\infty ic^i = \frac{c}{(1 - c)^2} \quad \vert c \vert < 1$ \\
+	$\sum\limits_{i = 0}^n c^i = \frac{c^{n + 1} - 1}{c - 1} \hfill c \neq 1$ &	
+	$\sum\limits_{i = 0}^\infty c^i = \frac{1}{1 - c} \hfill \vert c \vert < 1$ &
+	$\sum\limits_{i = 1}^\infty c^i = \frac{c}{1 - c} \hfill \vert c \vert < 1$ \\
 	\grayhline
-	
+		
 	\multicolumn{2}{|lI}{
 		$\sum\limits_{i = 0}^n ic^i = \frac{nc^{n + 2} - (n + 1)c^{n + 1} + c}{(c - 1)^2} \quad c \neq 1$
 	} &	
-	\multicolumn{2}{l|}{
+	$\sum\limits_{i = 0}^\infty ic^i = \frac{c}{(1 - c)^2} \hfill \vert c \vert < 1$ \\
+	\grayhline	
+	
+	\multicolumn{2}{|lI}{
 		$\sum\limits_{i = 1}^n iH_i = \frac{n(n + 1)}{2}H_n - \frac{n(n - 1)}{4}$
-	} \\
+	} &
+	$H_n = \sum\limits_{i = 1}^n \frac{1}{i}$ \\
 	\grayhline
 	
 	\multicolumn{2}{|lI}{
-		$\sum\limits_{i = 1}^n H_i = (n + 1)H_n - n$
-	} &
-	\multicolumn{2}{l|}{
 		$\sum\limits_{i = 1}^n \binom{i}{m}H_i =
 		\binom{n + 1}{m + 1} \left(H_{n + 1} - \frac{1}{m  + 1}\right)$
-	} \\
+	} &
+	$\sum\limits_{i = 1}^n H_i = (n + 1)H_n - n$ \\
 	\hline
 \end{tabularx}
+\end{expandtable}
diff --git a/content/math/tables/stuff.tex b/content/math/tables/stuff.tex
index 3cf8b4c..82f2d3f 100644
--- a/content/math/tables/stuff.tex
+++ b/content/math/tables/stuff.tex
@@ -1,6 +1,7 @@
-\begin{tabularx}{\linewidth}{|ll|}
+\begin{expandtable}
+\begin{tabularx}{\linewidth}{|Ll|}
 	\hline
-	\multicolumn{2}{|C|}{Verschiedenes} \\
+	\multicolumn{2}{|c|}{Verschiedenes} \\
 	\hline
 	Türme von Hanoi, minimale Schirttzahl: &
 	$T_n = 2^n - 1$ \\
@@ -20,7 +21,7 @@
 	\#Wälder mit $k$ gewurzelten Bäumen	&
 	$\frac{k}{n}\binom{n}{k}n^{n-k}$ \\
 
-	\#Wälder mit $k$ gewurzelten Bäumen mit vorgegebenen Wurzelknoten&
+	\#Wälder mit $k$ gewurzelten~Bäumen mit vorgegebenen Wurzelknoten&
 	$\frac{k}{n}n^{n-k}$ \\
 
 	Derangements &
@@ -29,4 +30,4 @@
 	$\lim\limits_{n \to \infty} \frac{!n}{n!} = \frac{1}{e}$ \\
 	\hline
 \end{tabularx}
-
+\end{expandtable}
diff --git a/content/tcr.tex b/content/tcr.tex
index b3cfb17..6d849d5 100644
--- a/content/tcr.tex
+++ b/content/tcr.tex
@@ -48,10 +48,7 @@
   \input{graph/graph}
   \input{geometry/geometry}
   \input{math/math}
-\end{multicols*}
   \clearpage
-  \input{math/tables}
-\begin{multicols*}{3}
   \input{string/string}
   \input{python/python}
   \input{other/other}
diff --git a/tcr.pdf b/tcr.pdf
index 7dc830e..dbd1055 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3


From cf3bf7ef7a3c4899b31041b15bcc67f6607f5cf4 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Tue, 10 Sep 2024 16:03:27 +0200
Subject: fix pentagonal number theorem

---
 content/math/math.tex |   2 +-
 tcr.pdf               | Bin 696378 -> 696416 bytes
 2 files changed, 1 insertion(+), 1 deletion(-)

(limited to 'content/math/math.tex')

diff --git a/content/math/math.tex b/content/math/math.tex
index c07a41e..bad3bad 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -485,7 +485,7 @@ Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$.
 \begin{align*}
 	p_0(0)=1 \qquad p_k(n)&=0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0\\
 	p_k(n)&= p_k(n-k) + p_{k-1}(n-1)\\[2pt]
-	p(n)&=\sum_{k=1}^{n} p_k(n)=p_n(2n)=\sum\limits_{k\neq0}^\infty(-1)^{k+1}p\bigg(n - \frac{k(3k-1)}{2}\bigg)
+	p(n)=\sum_{k=1}^{n} p_k(n)&=p_n(2n)=\sum\limits_{k\neq0}^\infty(-1)^{k+1}\bigg[p\bigg(n - \frac{k(3k-1)}{2}\bigg) + p\bigg(n - \frac{k(3k+1)}{2}\bigg)\bigg]
 \end{align*}
 \begin{itemize}
 	\item in Formel $3$ kann abgebrochen werden wenn $\frac{k(3k-1)}{2} > n$.
diff --git a/tcr.pdf b/tcr.pdf
index f97121c..d5cd7b1 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3


From d12405003fcbe53c26f024bbe1999fc59491046a Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Tue, 10 Sep 2024 16:10:54 +0200
Subject: fix pentagonal number theorem

---
 content/math/math.tex |   2 +-
 tcr.pdf               | Bin 696416 -> 696418 bytes
 2 files changed, 1 insertion(+), 1 deletion(-)

(limited to 'content/math/math.tex')

diff --git a/content/math/math.tex b/content/math/math.tex
index bad3bad..dd88a5b 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -485,7 +485,7 @@ Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$.
 \begin{align*}
 	p_0(0)=1 \qquad p_k(n)&=0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0\\
 	p_k(n)&= p_k(n-k) + p_{k-1}(n-1)\\[2pt]
-	p(n)=\sum_{k=1}^{n} p_k(n)&=p_n(2n)=\sum\limits_{k\neq0}^\infty(-1)^{k+1}\bigg[p\bigg(n - \frac{k(3k-1)}{2}\bigg) + p\bigg(n - \frac{k(3k+1)}{2}\bigg)\bigg]
+	p(n)=\sum_{k=1}^{n} p_k(n)&=p_n(2n)=\sum\limits_{k=1}^\infty(-1)^{k+1}\bigg[p\bigg(n - \frac{k(3k-1)}{2}\bigg) + p\bigg(n - \frac{k(3k+1)}{2}\bigg)\bigg]
 \end{align*}
 \begin{itemize}
 	\item in Formel $3$ kann abgebrochen werden wenn $\frac{k(3k-1)}{2} > n$.
diff --git a/tcr.pdf b/tcr.pdf
index d5cd7b1..9ed6eae 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3


From 36fa19a38cf9a357f04d4ed76f25b1cbf44deedb Mon Sep 17 00:00:00 2001
From: Lucas Schwebler <lucas.schwebler@gmail.com>
Date: Tue, 10 Sep 2024 21:50:42 +0200
Subject: new linear recurrence kthTerm code

---
 content/math/linearRecurence.cpp      |  33 -----------------
 content/math/linearRecurrence.cpp     |  30 +++++++++++++++
 content/math/linearRecurrenceOld.cpp  |  33 +++++++++++++++++
 content/math/math.tex                 |   5 ++-
 tcr.pdf                               | Bin 696418 -> 696332 bytes
 test/math/linearRecurence.cpp         |  54 ---------------------------
 test/math/linearRecurenceOld.cpp      |  54 +++++++++++++++++++++++++++
 test/math/linearRecurrence.cpp        |  57 +++++++++++++++++++++++++++++
 test/math/linearRecurrenceSlowMul.cpp |  67 ++++++++++++++++++++++++++++++++++
 9 files changed, 244 insertions(+), 89 deletions(-)
 delete mode 100644 content/math/linearRecurence.cpp
 create mode 100644 content/math/linearRecurrence.cpp
 create mode 100644 content/math/linearRecurrenceOld.cpp
 delete mode 100644 test/math/linearRecurence.cpp
 create mode 100644 test/math/linearRecurenceOld.cpp
 create mode 100644 test/math/linearRecurrence.cpp
 create mode 100644 test/math/linearRecurrenceSlowMul.cpp

(limited to 'content/math/math.tex')

diff --git a/content/math/linearRecurence.cpp b/content/math/linearRecurence.cpp
deleted file mode 100644
index 2501e64..0000000
--- a/content/math/linearRecurence.cpp
+++ /dev/null
@@ -1,33 +0,0 @@
-constexpr ll mod = 1'000'000'007;
-vector<ll> modMul(const vector<ll>& a, const vector<ll>& b,
-                  const vector<ll>& c) {
-	ll n = sz(c);
-	vector<ll> res(n * 2 + 1);
-	for (int i = 0; i <= n; i++) { //a*b
-		for (int j = 0; j <= n; j++) {
-			res[i + j] += a[i] * b[j];
-			res[i + j] %= mod;
-	}}
-	for (int i = 2 * n; i > n; i--) { //res%c
-		for (int j = 0; j < n; j++) {
-			res[i - 1 - j] += res[i] * c[j];
-			res[i - 1 - j] %= mod;
-	}}
-	res.resize(n + 1);
-	return res;
-}
-
-ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k) {
-	assert(sz(f) == sz(c));
-	vector<ll> tmp(sz(c) + 1), a(sz(c) + 1);
-	tmp[0] = a[1] = 1; //tmp = (x^k) % c
-
-	for (k++; k > 0; k /= 2) {
-		if (k & 1) tmp = modMul(tmp, a, c);
-		a = modMul(a, a, c);
-	}
-
-	ll res = 0;
-	for (int i = 0; i < sz(c); i++) res += (tmp[i+1] * f[i]) % mod;
-	return res % mod;
-}
diff --git a/content/math/linearRecurrence.cpp b/content/math/linearRecurrence.cpp
new file mode 100644
index 0000000..c15c25c
--- /dev/null
+++ b/content/math/linearRecurrence.cpp
@@ -0,0 +1,30 @@
+// constexpr ll mod = 998244353;
+// vector<ll> mul(const vector<ll> &a, const vector<ll> &b){
+// 	vector<ll> c(sz(a) + sz(b) - 1);
+// 	for(int i = 0; i < sz(a); i++){
+// 		for(int j = 0; j < sz(b); j++){
+// 			c[i+j] += a[i]*b[j] % mod;
+// 		}
+// 	}
+// 	for(ll &x : c) x %= mod;
+// 	return c;
+// }
+
+ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k){
+	int n = sz(c);
+	vector<ll> q(n+1, 1);
+	for(int i = 1; i <= n; i++) q[i] = (mod-c[i-1])%mod;
+	vector<ll> p = mul(f, q);
+	p.resize(n);
+	p.push_back(0);
+	do{
+		vector<ll> q2 = q;
+		for(int i = 1; i <= n; i += 2) q2[i] = (mod - q2[i]) % mod;
+		vector<ll> x = mul(p, q2), y = mul(q, q2);
+		for(int i = 0; i <= n; i++){
+			p[i] = i == n ? 0 : x[2*i + (k&1)];
+			q[i] = y[2*i];
+		}
+	}while(k /= 2);
+	return p[0];
+}
\ No newline at end of file
diff --git a/content/math/linearRecurrenceOld.cpp b/content/math/linearRecurrenceOld.cpp
new file mode 100644
index 0000000..2501e64
--- /dev/null
+++ b/content/math/linearRecurrenceOld.cpp
@@ -0,0 +1,33 @@
+constexpr ll mod = 1'000'000'007;
+vector<ll> modMul(const vector<ll>& a, const vector<ll>& b,
+                  const vector<ll>& c) {
+	ll n = sz(c);
+	vector<ll> res(n * 2 + 1);
+	for (int i = 0; i <= n; i++) { //a*b
+		for (int j = 0; j <= n; j++) {
+			res[i + j] += a[i] * b[j];
+			res[i + j] %= mod;
+	}}
+	for (int i = 2 * n; i > n; i--) { //res%c
+		for (int j = 0; j < n; j++) {
+			res[i - 1 - j] += res[i] * c[j];
+			res[i - 1 - j] %= mod;
+	}}
+	res.resize(n + 1);
+	return res;
+}
+
+ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k) {
+	assert(sz(f) == sz(c));
+	vector<ll> tmp(sz(c) + 1), a(sz(c) + 1);
+	tmp[0] = a[1] = 1; //tmp = (x^k) % c
+
+	for (k++; k > 0; k /= 2) {
+		if (k & 1) tmp = modMul(tmp, a, c);
+		a = modMul(a, a, c);
+	}
+
+	ll res = 0;
+	for (int i = 0; i < sz(c); i++) res += (tmp[i+1] * f[i]) % mod;
+	return res % mod;
+}
diff --git a/content/math/math.tex b/content/math/math.tex
index dd88a5b..fb66110 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -136,9 +136,10 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	Sei $f(n)=c_{0}f(n-1)+c_{1}f(n-2)+\dots + c_{n-1}f(0)$ eine lineare Rekurrenz.
 	
 	\begin{methods}
-		\method{kthTerm}{Berechnet $k$-ten Term einer Rekurrenz $n$-ter Ordnung}{\log(k)\cdot n^2}
+		\method{kthTerm}{Berechnet $k$-ten Term einer Rekurrenz $n$-ter Ordnung}{\log(k)\cdot \text{mul}(n)}
 	\end{methods}
-	\sourcecode{math/linearRecurence.cpp}
+	Die Polynom-Multiplikation kann auch mit NTT gemacht werden!
+	\sourcecode{math/linearRecurrence.cpp}
 	Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden:
 	$$\renewcommand\arraystretch{1.5}
 	\setlength\arraycolsep{3pt}
diff --git a/tcr.pdf b/tcr.pdf
index 9ed6eae..1bf4c26 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/test/math/linearRecurence.cpp b/test/math/linearRecurence.cpp
deleted file mode 100644
index a5290e5..0000000
--- a/test/math/linearRecurence.cpp
+++ /dev/null
@@ -1,54 +0,0 @@
-#include "../util.h"
-#include <math/linearRecurence.cpp>
-
-struct RandomRecurence {
-	vector<ll> f, c, cache;
-	RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {}
-
-	ll operator()(ll k){
-		while (sz(cache) <= k) {
-			ll cur = 0;
-			for (ll i = 0; i < sz(c); i++) {
-				cur += (c[i] * cache[sz(cache) - i - 1]) % mod;
-			}
-			cur %= mod;
-			cache.push_back(cur);
-		}
-		return cache[k];
-	}
-};
-
-void stress_test() {
-	int queries = 0;
-	for (int i = 0; i < 10'000; i++) {
-		int n = Random::integer<int>(1, 10);
-		RandomRecurence f(n);
-		for (int j = 0; j < 100; j++) {
-			ll k = Random::integer<ll>(0, 1000);
-
-			ll got = kthTerm(f.f, f.c, k);
-			ll expected = f(k);
-
-			if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
-			queries++;
-		}
-	}
-	cerr << "tested random queries: " << queries << endl;
-}
-
-constexpr int N = 1'000;
-void performance_test() {
-	timer t;
-	RandomRecurence f(N);
-	t.start();
-	hash_t hash = kthTerm(f.f, f.c, 1e18);
-	t.stop();
-	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
-	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
-}
-
-int main() {
-	stress_test();
-	performance_test();
-}
-
diff --git a/test/math/linearRecurenceOld.cpp b/test/math/linearRecurenceOld.cpp
new file mode 100644
index 0000000..dab2256
--- /dev/null
+++ b/test/math/linearRecurenceOld.cpp
@@ -0,0 +1,54 @@
+#include "../util.h"
+#include <math/linearRecurrenceOld.cpp>
+
+struct RandomRecurence {
+	vector<ll> f, c, cache;
+	RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {}
+
+	ll operator()(ll k){
+		while (sz(cache) <= k) {
+			ll cur = 0;
+			for (ll i = 0; i < sz(c); i++) {
+				cur += (c[i] * cache[sz(cache) - i - 1]) % mod;
+			}
+			cur %= mod;
+			cache.push_back(cur);
+		}
+		return cache[k];
+	}
+};
+
+void stress_test() {
+	int queries = 0;
+	for (int i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 10);
+		RandomRecurence f(n);
+		for (int j = 0; j < 100; j++) {
+			ll k = Random::integer<ll>(0, 1000);
+
+			ll got = kthTerm(f.f, f.c, k);
+			ll expected = f(k);
+
+			if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+			queries++;
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 1'000;
+void performance_test() {
+	timer t;
+	RandomRecurence f(N);
+	t.start();
+	hash_t hash = kthTerm(f.f, f.c, 1e18);
+	t.stop();
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/linearRecurrence.cpp b/test/math/linearRecurrence.cpp
new file mode 100644
index 0000000..50e98a0
--- /dev/null
+++ b/test/math/linearRecurrence.cpp
@@ -0,0 +1,57 @@
+#include "../util.h"
+#include <math/modPowIterativ.cpp>
+#include <math/transforms/ntt.cpp>
+#include <math/transforms/multiplyNTT.cpp>
+#include <math/linearRecurrence.cpp>
+
+struct RandomRecurence {
+	vector<ll> f, c, cache;
+	RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {}
+
+	ll operator()(ll k){
+		while (sz(cache) <= k) {
+			ll cur = 0;
+			for (ll i = 0; i < sz(c); i++) {
+				cur += (c[i] * cache[sz(cache) - i - 1]) % mod;
+			}
+			cur %= mod;
+			cache.push_back(cur);
+		}
+		return cache[k];
+	}
+};
+
+void stress_test() {
+	int queries = 0;
+	for (int i = 0; i < 1'000; i++) {
+		int n = Random::integer<int>(1, 10);
+		RandomRecurence f(n);
+		for (int j = 0; j < 100; j++) {
+			ll k = Random::integer<ll>(0, 1000);
+
+			ll got = kthTerm(f.f, f.c, k);
+			ll expected = f(k);
+
+			if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+			queries++;
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 100'000;
+void performance_test() {
+	timer t;
+	RandomRecurence f(N);
+	t.start();
+	hash_t hash = kthTerm(f.f, f.c, 1e18);
+	t.stop();
+	if (t.time > 8000) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/linearRecurrenceSlowMul.cpp b/test/math/linearRecurrenceSlowMul.cpp
new file mode 100644
index 0000000..205e584
--- /dev/null
+++ b/test/math/linearRecurrenceSlowMul.cpp
@@ -0,0 +1,67 @@
+#include "../util.h"
+
+constexpr ll mod = 998244353;
+vector<ll> mul(const vector<ll> &a, const vector<ll> &b){
+	vector<ll> c(sz(a) + sz(b) - 1);
+	for(int i = 0; i < sz(a); i++){
+		for(int j = 0; j < sz(b); j++){
+			c[i+j] += a[i]*b[j] % mod;
+		}
+	}
+	for(ll &x : c) x %= mod;
+	return c;
+}
+
+#include <math/linearRecurrence.cpp>
+
+struct RandomRecurence {
+	vector<ll> f, c, cache;
+	RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {}
+
+	ll operator()(ll k){
+		while (sz(cache) <= k) {
+			ll cur = 0;
+			for (ll i = 0; i < sz(c); i++) {
+				cur += (c[i] * cache[sz(cache) - i - 1]) % mod;
+			}
+			cur %= mod;
+			cache.push_back(cur);
+		}
+		return cache[k];
+	}
+};
+
+void stress_test() {
+	int queries = 0;
+	for (int i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 10);
+		RandomRecurence f(n);
+		for (int j = 0; j < 100; j++) {
+			ll k = Random::integer<ll>(0, 1000);
+
+			ll got = kthTerm(f.f, f.c, k);
+			ll expected = f(k);
+
+			if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+			queries++;
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 1'000;
+void performance_test() {
+	timer t;
+	RandomRecurence f(N);
+	t.start();
+	hash_t hash = kthTerm(f.f, f.c, 1e18);
+	t.stop();
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
-- 
cgit v1.2.3


From 0257f0b3c61f203f64c3817dfe19a08f6191517c Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Wed, 11 Sep 2024 00:29:27 +0200
Subject: moved stuff

---
 content/geometry/hpi.cpp          |  16 +++++++-------
 content/math/linearRecurrence.cpp |  14 ++++++------
 content/math/math.tex             |   7 +++++-
 content/math/recover.cpp          |  13 +++++++++++
 content/other/other.tex           |  18 ++++++----------
 content/other/recover.cpp         |  13 -----------
 tcr.pdf                           | Bin 698834 -> 695781 bytes
 test/geometry.h                   |   6 +++---
 test/math/recover.cpp             |  44 ++++++++++++++++++++++++++++++++++++++
 test/other/recover.cpp            |  44 --------------------------------------
 10 files changed, 87 insertions(+), 88 deletions(-)
 create mode 100644 content/math/recover.cpp
 delete mode 100644 content/other/recover.cpp
 create mode 100644 test/math/recover.cpp
 delete mode 100644 test/other/recover.cpp

(limited to 'content/math/math.tex')

diff --git a/content/geometry/hpi.cpp b/content/geometry/hpi.cpp
index c58a6e7..f3dc08d 100644
--- a/content/geometry/hpi.cpp
+++ b/content/geometry/hpi.cpp
@@ -27,22 +27,22 @@ struct hp {
 			if (ort == 0) return cross(from, to, a.from) < 0;
 			return cross(b.dir(), a.dir()) * ort > 0;
 		}
-		ll y = cross(a.dir(), b.dir());
-		ll z = cross(b.from - a.from, b.dir());
-		ptl i = mul(y, a.from) + mul(z, a.dir()); //intersect a and b
-		// check if i is outside/right of x
-		return imag(conj(mul(sgn(y),dir()))*(i-mul(y,from))) < 0;
+		ll x = cross(a.dir(), b.dir());
+		ll y = cross(b.from - a.from, b.dir());
+		ptl i = mul(x, a.from) + mul(y, a.dir()); //intersect a and b
+		// check if i is outside/right of this
+		return imag(conj(mul(sgn(x),dir()))*(i-mul(x,from))) < 0;
 	}
 };
 
 constexpr ll lim = 2e9+7;
 
 deque<hp> intersect(vector<hp> hps) {
-	hps.push_back(hp(pt{lim+1,-1}));
-	hps.push_back(hp(pt{lim+1,1}));
+	hps.push_back(hp(pt{lim + 1, -1}));
+	hps.push_back(hp(pt{lim + 1, 1}));
 	sort(all(hps));
 
-	deque<hp> dq = {hp(pt{-lim, 1})};
+	deque<hp> dq = {hp(pt{-lim - 1, 1})};
 	for (auto x : hps) {
 		while (sz(dq) > 1 && x.check(dq.end()[-1], dq.end()[-2]))
 			dq.pop_back();
diff --git a/content/math/linearRecurrence.cpp b/content/math/linearRecurrence.cpp
index c15c25c..ab86f71 100644
--- a/content/math/linearRecurrence.cpp
+++ b/content/math/linearRecurrence.cpp
@@ -10,21 +10,21 @@
 // 	return c;
 // }
 
-ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k){
+ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k) {
 	int n = sz(c);
-	vector<ll> q(n+1, 1);
-	for(int i = 1; i <= n; i++) q[i] = (mod-c[i-1])%mod;
+	vector<ll> q(n + 1, 1);
+	for (int i = 0; i < n; i++) q[i + 1] = (mod - c[i])%mod;
 	vector<ll> p = mul(f, q);
 	p.resize(n);
 	p.push_back(0);
-	do{
+	do {
 		vector<ll> q2 = q;
-		for(int i = 1; i <= n; i += 2) q2[i] = (mod - q2[i]) % mod;
+		for (int i = 1; i <= n; i += 2) q2[i] = (mod - q2[i]) % mod;
 		vector<ll> x = mul(p, q2), y = mul(q, q2);
-		for(int i = 0; i <= n; i++){
+		for (int i = 0; i <= n; i++){
 			p[i] = i == n ? 0 : x[2*i + (k&1)];
 			q[i] = y[2*i];
 		}
-	}while(k /= 2);
+	} while (k /= 2);
 	return p[0];
 }
\ No newline at end of file
diff --git a/content/math/math.tex b/content/math/math.tex
index fb66110..4ac6c9e 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -544,6 +544,11 @@ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \text
 \subsection{Wichtige Zahlen}
 \input{math/tables/composite}
 
+\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ }
+\method{recover}{findet $x$ und $y$ für $x=x\*y^{-1}\bmod m$}{\log(m)}
+\textbf{WICHTIG:} $x$ und $y$ müssen kleiner als $\sqrt{\nicefrac{m}{2}}$ sein!
+\sourcecode{math/recover.cpp}
+
 \optional{
 \subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
 \begin{methods}
@@ -552,10 +557,10 @@ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \text
 	\method{pi}{zählt Primzahlen  $\leq n$ ($n < N^2$)}{n^{2/3}}
 \end{methods}
 \sourcecode{math/piLehmer.cpp}
-}
 
 \subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
 \sourcecode{math/piLegendre.cpp}
+}
 
 \begin{algorithm}[optional]{Big Integers}
 	\sourcecode{math/bigint.cpp}
diff --git a/content/math/recover.cpp b/content/math/recover.cpp
new file mode 100644
index 0000000..1a593f0
--- /dev/null
+++ b/content/math/recover.cpp
@@ -0,0 +1,13 @@
+ll sq(ll x) {return x*x;}
+
+array<ll, 2> recover(ll c, ll m) {
+	array<ll, 2> u = {m, 0}, v = {c, 1};
+	while (m <= 2 * sq(v[0])) {
+		ll q = u[0] / v[0];
+		u[0] -= q * v[0];
+		u[1] -= q * v[1];
+		swap(u, v);
+	}
+	if (v[1] <= 0 || 2 * sq(v[1]) >= m) return {-1, -1};
+	return v;
+}
diff --git a/content/other/other.tex b/content/other/other.tex
index 368d0b3..191a6da 100644
--- a/content/other/other.tex
+++ b/content/other/other.tex
@@ -72,6 +72,12 @@
 	\sourcecode{other/sos.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Fast Subset Sum}
+	\method{fastSubsetSum}{findet maximale subset $\mathit{sum}\leq t$}{n \cdot A}
+	Die Laufzeit hängt vom maximalen Wert $A$ in der Menge ab.
+	\sourcecode{other/fastSubsetSum.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Parallel Binary Search}
 	\sourcecode{other/pbs.cpp}
 \end{algorithm}
@@ -95,18 +101,6 @@
 	\textbf{Beachte bei der Ausgabe, dass die Personen im ersten Fall von $\boldsymbol{1, \ldots, n}$ nummeriert sind, im zweiten Fall von $\boldsymbol{0, \ldots, n-1}$!}
 \end{algorithm}
 
-\vfill\null\columnbreak
-
-\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ }
-\method{recover}{findet $x$ und $y$ für $x=x\*y^{-1}\bmod m$}{\log(m)}
-\textbf{WICHTIG:} $x$ und $y$ müssen kleiner als $\sqrt{\nicefrac{m}{2}}$ sein!
-\sourcecode{other/recover.cpp}
-
-\subsection{Fast Subset Sum}
-\method{fastSubsetSum}{findet maximale subset sum $\leq t$}{n \cdot A}
-Die Laufzeit hängt vom maximalen Wert $A$ in der Menge ab.
-\sourcecode{other/fastSubsetSum.cpp}
-
 \begin{algorithm}[optional]{Zeileneingabe}
 	\sourcecode{other/split.cpp}
 \end{algorithm}
diff --git a/content/other/recover.cpp b/content/other/recover.cpp
deleted file mode 100644
index 1a593f0..0000000
--- a/content/other/recover.cpp
+++ /dev/null
@@ -1,13 +0,0 @@
-ll sq(ll x) {return x*x;}
-
-array<ll, 2> recover(ll c, ll m) {
-	array<ll, 2> u = {m, 0}, v = {c, 1};
-	while (m <= 2 * sq(v[0])) {
-		ll q = u[0] / v[0];
-		u[0] -= q * v[0];
-		u[1] -= q * v[1];
-		swap(u, v);
-	}
-	if (v[1] <= 0 || 2 * sq(v[1]) >= m) return {-1, -1};
-	return v;
-}
diff --git a/tcr.pdf b/tcr.pdf
index d383dd9..6f156e4 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/test/geometry.h b/test/geometry.h
index 7886fe2..0167d5c 100644
--- a/test/geometry.h
+++ b/test/geometry.h
@@ -1,6 +1,6 @@
-#include <geometry/sortAround.cpp>
-
 namespace details {
+	#include <geometry/sortAround.cpp>
+
 	// Liegt p auf der Strecke a-b?
 	bool pointInLineSegment(pt a, pt b, pt p) {
 		if (cross(a, b, p) != 0) return false;
@@ -59,7 +59,7 @@ namespace Random {
 			for (size_t i = 0; i < dirs.size(); i++) {
 				dirs[i] = pt(x[i], y[i]);
 			}
-			sortAround(0, dirs);
+			details::sortAround(0, dirs);
 
 			vector<pt> res = {{0, 0}};
 			ll maxX = 0;
diff --git a/test/math/recover.cpp b/test/math/recover.cpp
new file mode 100644
index 0000000..72853e5
--- /dev/null
+++ b/test/math/recover.cpp
@@ -0,0 +1,44 @@
+#include "../util.h"
+#include <other/recover.cpp>
+#include <math/shortModInv.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	timer t;
+	for (int i = 0; i < 500; i++) {
+		ll p = Random::prime<ll>(10000);
+		for (ll j = 0; 2*j*j < p; j++) {
+			for (ll b = 1; 2*b*b < p; b++) {
+				if (gcd(j, b) != 1) continue;
+				for (ll a : {-j, j}) {
+					ll c = a * multInv(b, p);
+					
+					t.start();
+					auto [x, y] = recover(c, p);
+					t.stop();
+
+					if (a != x || b != y) cerr << "got: " << x << "/" << y << ", expected: " << a << "/" << b << FAIL;
+					queries++;
+				}
+			}
+		}
+		for (ll c = 0; c < p; c++) {
+			t.start();
+			auto [x, y] = recover(c, p);
+			t.stop();
+
+			if (y < 0) continue;
+			if (y == 0) cerr << "error: y=0" << FAIL;
+			ll got = (((x * multInv(y, p)) % p) + p) % p;
+			if (got != c) cerr << "got: " << got << ", expected: " << c << FAIL;
+			queries++;
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms" << endl;
+}
+
+int main() {
+	stress_test();
+}
diff --git a/test/other/recover.cpp b/test/other/recover.cpp
deleted file mode 100644
index 72853e5..0000000
--- a/test/other/recover.cpp
+++ /dev/null
@@ -1,44 +0,0 @@
-#include "../util.h"
-#include <other/recover.cpp>
-#include <math/shortModInv.cpp>
-
-void stress_test() {
-	ll queries = 0;
-	timer t;
-	for (int i = 0; i < 500; i++) {
-		ll p = Random::prime<ll>(10000);
-		for (ll j = 0; 2*j*j < p; j++) {
-			for (ll b = 1; 2*b*b < p; b++) {
-				if (gcd(j, b) != 1) continue;
-				for (ll a : {-j, j}) {
-					ll c = a * multInv(b, p);
-					
-					t.start();
-					auto [x, y] = recover(c, p);
-					t.stop();
-
-					if (a != x || b != y) cerr << "got: " << x << "/" << y << ", expected: " << a << "/" << b << FAIL;
-					queries++;
-				}
-			}
-		}
-		for (ll c = 0; c < p; c++) {
-			t.start();
-			auto [x, y] = recover(c, p);
-			t.stop();
-
-			if (y < 0) continue;
-			if (y == 0) cerr << "error: y=0" << FAIL;
-			ll got = (((x * multInv(y, p)) % p) + p) % p;
-			if (got != c) cerr << "got: " << got << ", expected: " << c << FAIL;
-			queries++;
-		}
-	}
-	cerr << "tested random queries: " << queries << endl;
-	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
-	cerr << "tested performance: " << t.time << "ms" << endl;
-}
-
-int main() {
-	stress_test();
-}
-- 
cgit v1.2.3

