rearranged math

6 files changed, 126 insertions, 127 deletions

diff --git a/math/linearRecurence.cpp b/math/linearRecurence.cpp
index 83c4e05..3e1f812 100644
--- a/math/linearRecurence.cpp
+++ b/math/linearRecurence.cpp
@@ -1,5 +1,6 @@
 constexpr ll mod = 1000000007;
-vector<ll> modMul(const vector<ll>& a, const vector<ll>& b, const vector<ll>& c) {
+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
diff --git a/math/math.tex b/math/math.tex
index edaebd1..d648582 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -8,6 +8,25 @@
 	\sourcecode{math/longestIncreasingSubsequence.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Zykel Erkennung}
+	\begin{methods}
+		\method{cycleDetection}{findet Zyklus von $x_0$ und Länge in $f$}{b+l}
+	\end{methods}
+	\sourcecode{math/cycleDetection.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Permutationen}
+	\begin{methods}
+		\method{kthperm}{findet $k$-te Permutation \big($k \in [0, n!$)\big)}{n\*\log(n)}
+	\end{methods}
+	\sourcecode{math/kthperm.cpp}
+	\begin{methods}
+		\method{permIndex}{bestimmt Index der Permutation \big($\mathit{res} \in [0, n!$)\big)}{n\*\log(n)}
+	\end{methods}
+	\sourcecode{math/permIndex.cpp}
+\end{algorithm}
+\clearpage
+
 \subsection{Mod-Exponent und Multiplikation über $\boldsymbol{\mathbb{F}_p}$}
 %\vspace{-1.25em}
 %\begin{multicols}{2}
@@ -41,15 +60,6 @@
 \textbf{Sonst $\boldsymbol{\ggT(n, p) > 1}$:}\quad Es existiert kein $x^{-1}$.
 \sourcecode{math/multInv.cpp}
 
-\begin{algorithm}{Lineare Kongruenz}
-	\begin{itemize}
-		\item Löst $ax\equiv b\pmod{m}$.
-		\item Weitere Lösungen unterscheiden sich um \raisebox{2pt}{$\frac{m}{g}$}, es gibt
-		also $g$ Lösungen modulo $m$.
-	\end{itemize}
-	\sourcecode{math/linearCongruence.cpp}
-\end{algorithm}
-
 \paragraph{Lemma von \textsc{Bézout}}
 Sei $(x, y)$ eine Lösung der diophantischen Gleichung $ax + by = d$.
 Dann lassen sich wie folgt alle Lösungen berechnen:
@@ -66,73 +76,13 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	x_{k+1}&\coloneqq \overline{x}x_k+n\overline{y}y_k, & y_{k+1}&\coloneqq\overline{x}y_k+\overline{y}x_k
 \end{align*}
 
-
-\begin{algorithm}{Zykel Erkennung}
-	\begin{methods}
-		\method{cycleDetection}{findet Zyklus von $x_0$ und Länge in $f$}{b+l}
-	\end{methods}
-	\sourcecode{math/cycleDetection.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Permutationen}
-	\begin{methods}
-		\method{kthperm}{findet $k$-te Permutation \big($k \in [0, n!$)\big)}{n\*\log(n)}
-	\end{methods}
-	\sourcecode{math/kthperm.cpp}
-	\begin{methods}
-		\method{permIndex}{bestimmt Index der Permutation \big($\mathit{res} \in [0, n!$)\big)}{n\*\log(n)}
-	\end{methods}
-	\sourcecode{math/permIndex.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Lineare-Recurenz}
-	\begin{methods}
-		\method{BerlekampMassey}{Berechnet eine lineare Recurenz $n$-ter Ordnung}{n^2}
-		\method{}{aus den ersten $2n$ Werte}{}
-	\end{methods}
-	\sourcecode{math/berlekampMassey.cpp}
-	Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine lineare Recurenz.
-	
-	\begin{methods}
-		\method{kthTerm}{Berechnet $k$-ten Term einer Recurenz $n$-ter Ordnung}{\log(k)\cdot n^2}
-	\end{methods}
-	\sourcecode{math/linearRecurence.cpp}
-	Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden:
-	$$\renewcommand\arraystretch{1.5}
-	\setlength\arraycolsep{3pt}
-	\begin{pmatrix} 
-		c_{n-1} & c_{n-2} & \smash{\cdots} & \smash{\cdots} & c_0 \\
-		1 & 0 & \smash{\cdots} & \smash{\cdots} & 0 \\
-		0 & \smash{\ddots} & \smash{\ddots} & & \smash{\vdots} \\
-		0 & \smash{\ddots} & \smash{\ddots} & \smash{\ddots} & \smash{\vdots} \\
-		0 & \smash{\cdots} & 0 & 1 & 0 \\
-	\end{pmatrix}^k
-	\times~~
-	\begin{pmatrix} 
-		f(n-1) \\
-		f(n-2) \\
-		\smash{\vdots} \\
-		\smash{\vdots} \\
-		f(0) \\
-	\end{pmatrix}
-	~~=~~
-	\begin{pmatrix} 
-		f(n-1+k) \\
-		f(n-2+k) \\
-		\smash{\vdots} \\
-		\smash{\vdots} \\
-		f(k) \makebox[0pt][l]{\hspace{15pt}$\vcenter{\hbox{\huge$\leftarrow$}}$}\\
-	\end{pmatrix}
-	$$
-\end{algorithm}
-
-
-\begin{algorithm}{Matrix-Exponent}
-	\begin{methods}
-		\method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3}
-		\method{calc}{berechnet $m^b_{y,x}$}{\log(b)\cdot n^2}
-	\end{methods}
-	\sourcecode{math/matrixPower.cpp}
+\begin{algorithm}{Lineare Kongruenz}
+	\begin{itemize}
+		\item Löst $ax\equiv b\pmod{m}$.
+		\item Weitere Lösungen unterscheiden sich um \raisebox{2pt}{$\frac{m}{g}$}, es gibt
+		also $g$ Lösungen modulo $m$.
+	\end{itemize}
+	\sourcecode{math/linearCongruence.cpp}
 \end{algorithm}
 
 \begin{algorithm}{Chinesischer Restsatz}
@@ -140,9 +90,9 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 		\item Extrem anfällig gegen Overflows. Evtl. häufig 128-Bit Integer verwenden.
 		\item Direkte Formel für zwei Kongruenzen $x \equiv a \bmod n$, $x \equiv b \bmod m$:
 		\[
-			x \equiv a - y \cdot n \cdot \frac{a - b}{d} \bmod \frac{mn}{d}
-			\qquad \text{mit} \qquad
-			d := \ggT(n, m) = yn + zm
+		x \equiv a - y \cdot n \cdot \frac{a - b}{d} \bmod \frac{mn}{d}
+		\qquad \text{mit} \qquad
+		d := \ggT(n, m) = yn + zm
 		\]
 		Formel kann auch für nicht teilerfremde Moduli verwendet werden.
 		Sind die Moduli nicht teilerfremd, existiert genau dann eine Lösung,
@@ -153,10 +103,18 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/chineseRemainder.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Primzahltest \& Faktorisierung}
+	\method{isPrime}{prüft ob Zahl prim ist}{\log(n)^2}
+	\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}
 	\begin{methods}
-		\method{countDivisors}{Zählt Teiler von $n$}{n^\frac{1}{3}}
-		\method{isPrime}{prüft ob Zahl prim ist}{1}
+		\method{countDivisors}{Zählt Teiler von $n$}{\sqrt[\leftroot{3}\uproot{2}3]{n}}
 	\end{methods}
 	\sourcecode{math/divisors.cpp}
 \end{algorithm}
@@ -191,32 +149,10 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/discreteNthRoot.cpp}
 \end{algorithm}
 
-\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
-\begin{methods}
-	\method{init}{berechnet $\pi$ bis $N$}{N\*\log(\log(N))}
-	\method{phi}{zählt zu $p_i$ teilerfremde Zahlen $\leq n$ für alle $i \leq k$}{???}
-	\method{pi}{zählt Primzahlen  $\leq n$ ($n < N^2$)}{n^{2/3}}
-\end{methods}
-\sourcecode{math/piLehmer.cpp}
-\clearpage
 
-\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$}
-\method{gauss}{löst LGS}{n^3}
-\sourcecode{math/lgsFp.cpp}
 
-\subsection{LGS über $\boldsymbol{\mathbb{R}}$}
-\sourcecode{math/gauss.cpp}
 
 
-\begin{algorithm}{Primzahltest \& Faktorisierung}
-	\method{isPrime}{prüft ob Zahl prim ist}{\log(n)^2}
-	\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}{Primzahlsieb von \textsc{Eratosthenes}}
 	\begin{itemize}
 		\item Kann erweitert werden: Für jede Zahl den \{kleinsten, größten\} Primfaktor speichern, Liste von Primzahlen berechnen
@@ -247,25 +183,40 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	Die Anzahl der Subsequences mit $\ggT=1$ ist gegeben durch $\sum_{i = 1}^N \mu(i) \cdot (2^{cnt[i]} - 1)$.
 	\sourcecode{math/mobius.cpp}
 \end{algorithm}
-\clearpage
 
+\columnbreak
 \subsection{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion}
 \begin{itemize}
 	\item Zählt die relativ primen Zahlen $\leq n$.
-
+	
 	\item Multiplikativ:
 	$\gcd(a,b) = 1 \Longrightarrow \varphi(a) \cdot \varphi(b) = \varphi(ab)$
-
+	
 	\item $p$ prim, $k \in \mathbb{N}$:
 	$~\varphi(p^k) = p^k - p^{k - 1}$
-
+	
 	\item \textbf{\textsc{Euler}'s Theorem:}
-		Für $b \geq \varphi(c)$ gilt: $a^b \equiv a^{b \bmod \varphi(c) + \varphi(c)} \pmod{c}$. Darüber hinaus gilt: $\gcd(a, c) = 1 \Leftrightarrow a^b \equiv a^{b \bmod \varphi(c)} \pmod{c}$.
+	Für $b \geq \varphi(c)$ gilt: $a^b \equiv a^{b \bmod \varphi(c) + \varphi(c)} \pmod{c}$. Darüber hinaus gilt: $\gcd(a, c) = 1 \Leftrightarrow a^b \equiv a^{b \bmod \varphi(c)} \pmod{c}$.
 	Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}:
 	$a^{m} \equiv a \pmod{m}$
 \end{itemize}
 \sourcecode{math/phi.cpp}
 
+\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$}
+\method{gauss}{löst LGS}{n^3}
+\sourcecode{math/lgsFp.cpp}
+
+\subsection{LGS über $\boldsymbol{\mathbb{R}}$}
+\sourcecode{math/gauss.cpp}
+
+\begin{algorithm}{Numerisch Extremstelle bestimmen}
+	\sourcecode{math/goldenSectionSearch.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Numerisch Integrieren, Simpsonregel}
+	\sourcecode{math/simpson.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}
 	Multipliziert Polynome $A$ und $B$.
 	\begin{itemize}
@@ -285,13 +236,63 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	Multiplikation mit 2 transforms statt 3: (nur benutzten wenn nötig!)
 	\sourcecode{math/transforms/fftMul.cpp}
 \end{algorithm}
+\clearpage
 
-\begin{algorithm}{Numerisch Extremstelle bestimmen}
-	\sourcecode{math/goldenSectionSearch.cpp}
+\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
+\begin{methods}
+	\method{init}{berechnet $\pi$ bis $N$}{N\*\log(\log(N))}
+	\method{phi}{zählt zu $p_i$ teilerfremde Zahlen $\leq n$ für alle $i \leq k$}{???}
+	\method{pi}{zählt Primzahlen  $\leq n$ ($n < N^2$)}{n^{2/3}}
+\end{methods}
+\sourcecode{math/piLehmer.cpp}
+
+\begin{algorithm}{Lineare-Recurenz}
+	\begin{methods}
+		\method{BerlekampMassey}{Berechnet eine lineare Recurenz $n$-ter Ordnung}{n^2}
+		\method{}{aus den ersten $2n$ Werte}{}
+	\end{methods}
+	\sourcecode{math/berlekampMassey.cpp}
+	Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine lineare Recurenz.
+	
+	\begin{methods}
+		\method{kthTerm}{Berechnet $k$-ten Term einer Recurenz $n$-ter Ordnung}{\log(k)\cdot n^2}
+	\end{methods}
+	\sourcecode{math/linearRecurence.cpp}
+	Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden:
+	$$\renewcommand\arraystretch{1.5}
+	\setlength\arraycolsep{3pt}
+	\begin{pmatrix} 
+		c_{n-1} & c_{n-2} & \smash{\cdots} & \smash{\cdots} & c_0 \\
+		1 & 0 & \smash{\cdots} & \smash{\cdots} & 0 \\
+		0 & \smash{\ddots} & \smash{\ddots} & & \smash{\vdots} \\
+		0 & \smash{\ddots} & \smash{\ddots} & \smash{\ddots} & \smash{\vdots} \\
+		0 & \smash{\cdots} & 0 & 1 & 0 \\
+	\end{pmatrix}^k
+	\times~~
+	\begin{pmatrix} 
+		f(n-1) \\
+		f(n-2) \\
+		\smash{\vdots} \\
+		\smash{\vdots} \\
+		f(0) \\
+	\end{pmatrix}
+	~~=~~
+	\begin{pmatrix} 
+		f(n-1+k) \\
+		f(n-2+k) \\
+		\smash{\vdots} \\
+		\smash{\vdots} \\
+		f(k) \makebox[0pt][l]{\hspace{15pt}$\vcenter{\hbox{\huge$\leftarrow$}}$}\\
+	\end{pmatrix}
+	$$
 \end{algorithm}
 
-\begin{algorithm}{Numerisch Integrieren, Simpsonregel}
-	\sourcecode{math/simpson.cpp}
+\begin{algorithm}{Matrix-Exponent}
+	\begin{methods}
+		\method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3}
+		\method{calc}{berechnet $m^b_{y,x}$}{\log(b)\cdot n^2}
+	\end{methods}
+	\sourcecode{math/matrixPower.cpp}
 \end{algorithm}
 
 \begin{algorithm}{\textsc{Legendre}-Symbol}
@@ -375,7 +376,7 @@ so gilt
 		\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 Möglichkeiten ein konvexes Polygon mit $n + 2$ Ecken zu triangulieren.
 		\item Anzahl der monotonen Pfade (zwischen gegenüberliegenden Ecken) in
 		einem $n \times n$-Gitter, die nicht die Diagonale kreuzen.
 	\end{itemize}
diff --git a/math/millerRabin.cpp b/math/millerRabin.cpp
index e9ac9ea..e4d2f6e 100644
--- a/math/millerRabin.cpp
+++ b/math/millerRabin.cpp
@@ -1,20 +1,19 @@
 constexpr ll bases32[] = {2, 7, 61};
 constexpr ll bases64[] = {2, 325, 9375, 28178, 450775, 
                           9780504, 1795265022};
-
 bool isPrime(ll n) {
-	if(n < 2 || n % 2 == 0) return n == 2;
+	if (n < 2 || n % 2 == 0) return n == 2;
 	ll d = n - 1, j = 0;
-	while(d % 2 == 0) d /= 2, j++;
-	for(ll a : bases64) {
+	while (d % 2 == 0) d /= 2, j++;
+	for (ll a : bases64) {
 		if (a % n == 0) continue;
 		ll v = powMod(a, d, n); //with mulmod or int128
-		if(v == 1 || v == n - 1) continue;
-		for(ll i = 1; i <= j; i++) {
+		if (v == 1 || v == n - 1) continue;
+		for (ll i = 1; i <= j; i++) {
 			v = (v * v) % n; //mulmod or int128
-			if(v == n - 1 || v <= 1) break;
+			if (v == n - 1 || v <= 1) break;
 		}
-		if(v != n - 1) return false;
+		if (v != n - 1) return false;
 	}
 	return true;
 }
diff --git a/math/rho.cpp b/math/rho.cpp
index 865a438..df70251 100644
--- a/math/rho.cpp
+++ b/math/rho.cpp
@@ -3,7 +3,7 @@ ll rho(ll n) { // Findet Faktor < n, nicht unbedingt prim.
 	if (n % 2 == 0) return 2;
 	ll x = 0, y = 0, prd = 2;
 	auto f = [n](lll x){return (x * x) % n + 1;};
-	for (ll t = 30, i = n / 2 + 7; t % 40 || gcd(prd, n) == 1; t++) {
+	for (ll t = 30, i = n/2 + 7; t % 40 || gcd(prd, n) == 1; t++) {
 		if (x == y) x = ++i, y = f(x);
 		if (ll q = (lll)prd * abs(x-y) % n; q) prd = q;
 		x = f(x); y = f(f(y));
@@ -15,6 +15,5 @@ void factor(ll n, map<ll, int>& facts) {
 	if (n == 1) return;
 	if (isPrime(n)) {facts[n]++, return;}
 	ll f = rho(n);
-	factor(n / f, facts);
-	factor(f, facts);
+	factor(n / f, facts); factor(f, facts);
 }
diff --git a/math/transforms/all.cpp b/math/transforms/all.cpp
index 22cd5b5..66e6a41 100644
--- a/math/transforms/all.cpp
+++ b/math/transforms/all.cpp
@@ -3,8 +3,7 @@ constexpr ll root = 3;*/
 
 using cplx = complex<double>;
 
-@\hl{NTT, xor, or, and}@
-//void fft(vector<ll> &a, bool inverse = 0) {
+//void fft(vector<ll> &a, bool inverse = 0) { @\hl{NTT, xor, or, and}@
 void fft(vector<cplx>& a, bool inverse = 0) {
 	int n = a.size();
 	for (int i = 0, j = 1; j < n - 1; ++j) {
diff --git a/tcr.pdf b/tcr.pdf
index 736dbf0..396adc7 100644
--- a/tcr.pdf
+++ b/tcr.pdf