8 files changed, 46 insertions, 18 deletions

diff --git a/math/binomial0.cpp b/math/binomial0.cpp
index 896a0f1..f37aea5 100644
--- a/math/binomial0.cpp
+++ b/math/binomial0.cpp
@@ -10,5 +10,5 @@ void precalc() {
 
 ll calc_binom(ll n, ll k) {
 	if (n < 0 || n < k || k < 0) return 0;
-	return (inv[n] * inv[n-k] % mod) * fac[k] % mod;
+	return (fac[n] * inv[n-k] % mod) * inv[k] % mod;
 }
diff --git a/math/linearRecurence.cpp b/math/linearRecurrence.cpp
index 2501e64..2501e64 100644
--- a/math/linearRecurence.cpp
+++ b/math/linearRecurrence.cpp
diff --git a/math/math.tex b/math/math.tex
index c157e1b..f5fbdca 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -25,7 +25,7 @@
 	\end{methods}

 	\sourcecode{math/permIndex.cpp}

 \end{algorithm}

-\clearpage

+\columnbreak

 

 \subsection{Mod-Exponent und Multiplikation über $\boldsymbol{\mathbb{F}_p}$}

 %\vspace{-1.25em}

@@ -41,6 +41,11 @@
 	\item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten!

 \end{itemize}

 

+\begin{algorithm}[optional]{Square root modulo prime}

+	\sourcecode{math/modSqrt.cpp}

+	\sourcecode{math/sqrtModCipolla.cpp}

+\end{algorithm}

+

 \begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus}

 	\runtime{\log(a) + \log(b)}

 	\sourcecode{math/extendedEuclid.cpp}

@@ -142,7 +147,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/discreteNthRoot.cpp}

 \end{algorithm}

 

-

 \begin{algorithm}{Primitivwurzeln}

 	\begin{itemize}

 		\item Primitivwurzel modulo $n$ existiert $\Leftrightarrow$ $n \in \{2,\ 4,\ p^\alpha,\ 2\cdot p^\alpha \mid\ 2 < p \in \mathbb{P},\ \alpha \in \mathbb{N}\}$

@@ -158,21 +162,21 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/primitiveRoot.cpp}

 \end{algorithm}

 

-\begin{algorithm}{Linearessieb und Multiplikative Funktionen}

+\begin{algorithm}{Lineares Sieb und multiplikative Funktionen}

 	Eine (zahlentheoretische) Funktion $f$ heißt multiplikativ wenn $f(1)=1$ und $f(a\cdot b)=f(a)\cdot f(b)$, falls $\ggT(a,b)=1$.

 	

 	$\Rightarrow$ Es ist ausreichend $f(p^k)$ für alle primen $p$ und alle $k$ zu kennen.

 	

 	\begin{methods}

 		\method{sieve}{berechnet Primzahlen und co.}{N}

-		\method{sieved}{Wert der endsprechenden Multiplikativen Funktion}{1}

+		\method{sieved}{Wert der entsprechenden multiplikativen Funktion}{1}

 		

-		\method{naive}{Wert der endsprechenden Multiplikativen Funktion}{\sqrt{n}}

+		\method{naive}{Wert der entsprechenden multiplikativen Funktion}{\sqrt{n}}

 	\end{methods}

 	\textbf{Wichtig:} Sieb rechts ist schneller für \code{isPrime} oder \code{primes}!

 	

 	\sourcecode{math/linearSieve.cpp}

-	\textbf{\textsc{Möbius}-Funtkion:}

+	\textbf{\textsc{Möbius} Funktion:}

 	\begin{itemize}

 		\item $\mu(n)=+1$, falls $n$ quadratfrei ist und gerade viele Primteiler hat

 		\item $\mu(n)=-1$, falls $n$ quadratfrei ist und ungerade viele Primteiler hat

@@ -185,7 +189,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 		\item $p$ prim, $k \in \mathbb{N}$:

 		$~\varphi(p^k) = p^k - p^{k - 1}$

 		

-		\item \textbf{Euler's Theorem:}

+		\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}$.

 		Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}:

 		$a^{m} \equiv a \pmod{m}$

@@ -324,7 +328,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\begin{methods}

 		\method{kthTerm}{Berechnet $k$-ten Term einer Rekurrenz $n$-ter Ordnung}{\log(k)\cdot n^2}

 	\end{methods}

-	\sourcecode{math/linearRecurence.cpp}

+	\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}

@@ -379,7 +383,7 @@ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \text
 

 \subsection{Kombinatorik}

 

-\paragraph{Wilsons Theorem}

+\paragraph{\textsc{Wilson}'s Theorem}

 A number $n$ is prime if and only if

 $(n-1)!\equiv -1\bmod{n}$.\\

 ($n$ is prime if and only if $(m-1)!\cdot(n-m)!\equiv(-1)^m\bmod{n}$ for all $m$ in $\{1,\dots,n\}$)

@@ -391,14 +395,14 @@ $(n-1)!\equiv -1\bmod{n}$.\\
 	\end{cases}

 \end{align*}

 

-\paragraph{\textsc{Zeckendorfs} Theorem}

+\paragraph{\textsc{Zeckendorf}'s Theorem}

 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.

 

-\paragraph{\textsc{Lucas}-Theorem}

+\paragraph{\textsc{Lucas}'s Theorem}

 Ist $p$ prim, $m=\sum_{i=0}^km_ip^i$, $n=\sum_{i=0}^kn_ip^i$ ($p$-adische Darstellung),

 so gilt

 \vspace{-0.75\baselineskip}

@@ -409,7 +413,7 @@ so gilt
 %\begin{algorithm}{Binomialkoeffizienten}

 \paragraph{Binomialkoeffizienten}

 	Die Anzahl der \mbox{$k$-elementigen} Teilmengen einer \mbox{$n$-elementigen} Menge.

-	

+

 	\begin{methods}

 		\method{precalc}{berechnet $n!$ und $n!^{-1}$ vor}{\mathit{lim}}

 		\method{calc\_binom}{berechnet Binomialkoeffizient}{1}

diff --git a/math/shortModInv.cpp b/math/shortModInv.cpp
index 244bacf..f696cce 100644
--- a/math/shortModInv.cpp
+++ b/math/shortModInv.cpp
@@ -1,3 +1,3 @@
 ll multInv(ll x, ll m) { // x^{-1} mod m
-    return 1 < x ? m - inv(m % x, x) * m / x : 1;
+    return 1 < x ? m - multInv(m % x, x) * m / x : 1;
 }
diff --git a/math/tables.tex b/math/tables.tex
index 53f3758..c422d73 100644
--- a/math/tables.tex
+++ b/math/tables.tex
@@ -1,8 +1,12 @@
 \enlargethispage{0.2cm}
 \begin{multicols*}{2}
+	\refstepcounter{subsection}
+	\subsectionmark{Tables}
+	\addcontentsline{toc}{subsection}{\protect\numberline{\thesubsection}Tables}
+
 	\input{math/tables/binom}
 	\vfill
-	\input{math/tables/composite}
+	\input{math/tables/prime-composite}
 	\vfill
 	\input{math/tables/platonic}
 	\vfill
diff --git a/math/tables/composite.tex b/math/tables/prime-composite.tex
index 8e14b2e..4c32c7d 100644
--- a/math/tables/composite.tex
+++ b/math/tables/prime-composite.tex
@@ -1,5 +1,4 @@
-
-\begin{tabularx}{\linewidth}{|r||r|r||r|r|r||C|}
+\begin{tabularx}{\linewidth}{|r|rIr|rIrIr|C|}
 	\hline
 	\multicolumn{7}{|c|}{Important Numbers} \\
 	\hline
diff --git a/math/tables/stuff.tex b/math/tables/stuff.tex
index 5b5093e..3cf8b4c 100644
--- a/math/tables/stuff.tex
+++ b/math/tables/stuff.tex
@@ -23,7 +23,7 @@
 	\#Wälder mit $k$ gewurzelten Bäumen mit vorgegebenen Wurzelknoten&
 	$\frac{k}{n}n^{n-k}$ \\
 
-	Dearangements &
+	Derangements &
 	$!n = (n - 1)(!(n - 1) + !(n - 2)) = \left\lfloor\frac{n!}{e} + \frac{1}{2}\right\rfloor$ \\
 	&
 	$\lim\limits_{n \to \infty} \frac{!n}{n!} = \frac{1}{e}$ \\
diff --git a/math/test/binomial0.cpp b/math/test/binomial0.cpp
new file mode 100644
index 0000000..d6c3a03
--- /dev/null
+++ b/math/test/binomial0.cpp
@@ -0,0 +1,21 @@
+constexpr ll mod = 1'000'000'007;
+
+#include "../shortModInv.cpp"
+#include "../binomial0.cpp"
+
+int main() {
+	precalc();
+	assert(calc_binom(5, -1) == 0);
+	assert(calc_binom(5, 0) == 1);
+	assert(calc_binom(5, 1) == 5);
+	assert(calc_binom(5, 2) == 10);
+	assert(calc_binom(5, 3) == 10);
+	assert(calc_binom(5, 4) == 5);
+	assert(calc_binom(5, 5) == 1);
+	assert(calc_binom(5, 6) == 0);
+	assert(calc_binom(0, 0) == 1);
+	assert(calc_binom(-1, 0) == 0);
+	assert(calc_binom(-1, -1) == 0);
+	assert(calc_binom(-1, -2) == 0);
+	assert(calc_binom(100'000, 50'000) == 149033233);
+}