From 1a0fba268ca9ef390a45c86a94a27edf026a4f67 Mon Sep 17 00:00:00 2001 From: Gloria Mundi Date: Thu, 20 Nov 2025 17:58:00 +0100 Subject: normalize newlines --- content/math/math.tex | 1190 ++++++++++++++++++++++----------------------- content/math/piLehmer.cpp | 104 ++-- 2 files changed, 647 insertions(+), 647 deletions(-) (limited to 'content/math') diff --git a/content/math/math.tex b/content/math/math.tex index bcb4275..1bcf85d 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -1,595 +1,595 @@ -\section{Mathe} - -\begin{algorithm}{Longest Increasing Subsequence} - \begin{itemize} - \item \code{lower\_bound} $\Rightarrow$ streng monoton - \item \code{upper\_bound} $\Rightarrow$ monoton - \end{itemize} - \sourcecode{math/longestIncreasingSubsequence.cpp} -\end{algorithm} -\columnbreak - -\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} -\columnbreak - -\subsection{Potenzen in $\boldsymbol{\mathbb{Z}/n\mathbb{Z}}$} - \begin{methods} - \method{powMod}{berechnet $a^b \bmod n$}{\log(b)} - \end{methods} - \sourcecode{math/modPowIterativ.cpp} - \begin{itemize} - \item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten! - \end{itemize} - -\optional{ -\subsection{Multiplikation in $\boldsymbol{\mathbb{Z}/n\mathbb{Z}}$ \opthint} - \begin{methods} - \method{mulMod}{berechnet $a \cdot b \bmod n$}{\log(b)} - \end{methods} - \sourcecode{math/modMulIterativ.cpp} -} - -\begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus} - \runtime{\log(a) + \log(b)} - \sourcecode{math/extendedEuclid.cpp} -\end{algorithm} - -\subsection{Multiplikatives Inverses von $\boldsymbol{x}$ in $\boldsymbol{\mathbb{Z}/m\mathbb{Z}}$} -\textbf{Falls $\boldsymbol{m}$ prim:}\quad $x^{-1} \equiv x^{m-2} \bmod m$ - -\textbf{Falls $\boldsymbol{\ggT(x, m) = 1}$:} -\begin{itemize} - \item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit - $\alpha x + \beta m = 1$. - \item Nach Kongruenz gilt $\alpha x + \beta m \equiv \alpha x \equiv 1 \bmod m$. - \item $x^{-1} :\equiv \alpha \bmod m$ -\end{itemize} -\textbf{Sonst $\boldsymbol{\ggT(x, m) > 1}$:}\quad Es existiert kein $x^{-1}$. -% \sourcecode{math/multInv.cpp} -\sourcecode{math/shortModInv.cpp} - -\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: -\[ -\left(x + k\frac{b}{\ggT(a, b)},~y - k\frac{a}{\ggT(a, b)}\right) -\] - -\paragraph{\textsc{Pell}-Gleichungen} -Sei $(\overline{x}, \overline{y})$ die Lösung von $x^2 - ny^2 = 1$, die $x>1$ minimiert. -Sei $(\tilde{x}, \tilde{y})$ die Lösung von $x^2-ny^2 = c$, die $x>1$ minimiert. Dann lassen -sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: -\begin{align*} - x_1&\coloneqq \tilde{x}, & y_1&\coloneqq\tilde{y}\\ - 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}{Lineare Kongruenz} - \begin{itemize} - \item Kleinste Lösung $x$ für $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} - \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 \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 - \] - Formel kann auch für nicht teilerfremde Moduli verwendet werden. - Sind die Moduli nicht teilerfremd, existiert genau dann eine Lösung, - wenn $a\equiv~b \bmod \ggT(m, n)$. - In diesem Fall sind keine Faktoren - auf der linken Seite erlaubt. - \end{itemize} - \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} -\end{algorithm} - -\begin{algorithm}{Teiler} - \begin{methods} - \method{countDivisors}{Zählt Teiler von $n$}{\sqrt[\leftroot{3}\uproot{2}3]{n}} - \end{methods} - \sourcecode{math/divisors.cpp} -\end{algorithm} - -\begin{algorithm}{Matrix-Exponent} - \begin{methods} - \method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3} - \method{calc}{berechnet $m^b \cdot v$}{\log(b)\cdot n^2} - \end{methods} - \textbf{Tipp:} wenn \code{v[x]=1} und \code{0} sonst, dann ist \code{res[y]} = $m^b_{y,x}$. - \sourcecode{math/matrixPower.cpp} -\end{algorithm} - -\begin{algorithm}{Lineare Rekurrenz} - \begin{methods} - \method{BerlekampMassey}{Berechnet eine lineare Rekurrenz $n$-ter Ordnung}{n^2} - \method{}{aus den ersten $2n$ Werte}{} - \end{methods} - \sourcecode{math/berlekampMassey.cpp} - 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 \text{mul}(n)} - \end{methods} - 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} - \begin{pmatrix} - c_{0} & c_{1} & \smash{\cdots} & \smash{\cdots} & c_{n-1} \\ - 1 & 0 & \smash{\cdots} & \smash{\cdots} & 0 \\ - 0 & \smash{\ddots} & \smash{\ddots} & & \smash{\vdots} \\ - \smash{\vdots} & \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}{Diskreter Logarithmus} - \begin{methods} - \method{solve}{bestimmt Lösung $x$ für $a^x=b \bmod m$}{\sqrt{m}\*\log(m)} - \end{methods} - \sourcecode{math/discreteLogarithm.cpp} -\end{algorithm} - -\begin{algorithm}{Diskrete Quadratwurzel} - \begin{methods} - \method{sqrtMod}{bestimmt Lösung $x$ für $x^2=a \bmod p$ }{\log(p)} - \end{methods} - \textbf{Wichtig:} $p$ muss prim sein! - \sourcecode{math/sqrtModCipolla.cpp} -\end{algorithm} -%\columnbreak - -\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}\}$ - \item es existiert entweder keine oder $\varphi(\varphi(n))$ inkongruente Primitivwurzeln - \item Sei $g$ Primitivwurzel modulo $n$. - Dann gilt:\newline - Das kleinste $k$, sodass $g^k \equiv 1 \bmod n$, ist $k = \varphi(n)$. - \end{itemize} - \begin{methods} - \method{isPrimitive}{prüft ob $g$ eine Primitivwurzel ist}{\log(\varphi(n))\*\log(n)} - \method{findPrimitive}{findet Primitivwurzel (oder -1)}{\abs{ans}\*\log(\varphi(n))\*\log(n)} - \end{methods} - \sourcecode{math/primitiveRoot.cpp} -\end{algorithm} - -\begin{algorithm}{Diskrete \textrm{\textit{n}}-te Wurzel} - \begin{methods} - \method{root}{bestimmt Lösung $x$ für $x^a=b \bmod m$ }{\sqrt{m}\*\log(m)} - \end{methods} - Alle Lösungen haben die Form $g^{c + \frac{i \cdot \phi(n)}{\gcd(a, \phi(n))}}$ - \sourcecode{math/discreteNthRoot.cpp} -\end{algorithm} - -\begin{algorithm}{\textsc{Legendre}-Symbol} - Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$: - \vspace{-0.15cm}\begin{align*} - \hspace*{3cm}\legendre{a}{p} &= - \begin{cases*} - \hphantom{-}0 & falls $p~\vert~a$ \\[-1ex] - \hphantom{-}1 & falls $\exists x \in \mathbb{Z}\backslash p\mathbb{Z} : a \equiv x^2 \bmod p$ \\[-1ex] - -1 & sonst - \end{cases*} \\ - \legendre{-1}{p} = (-1)^{\frac{p - 1}{2}} &= - \begin{cases*} - \hphantom{-}1 & falls $p \equiv 1 \bmod 4$ \\[-1ex] - -1 & falls $p \equiv 3 \bmod 4$ - \end{cases*} \\ - \legendre{2}{p} = (-1)^{\frac{p^2 - 1}{8}} &= - \begin{cases*} - \hphantom{-}1 & falls $p \equiv \pm 1 \bmod 8$ \\[-1ex] - -1 & falls $p \equiv \pm 3 \bmod 8$ - \end{cases*} - \end{align*} - \begin{align*} - \legendre{p}{q} \cdot \legendre{q}{p} = (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} && - \legendre{a}{p} \equiv a^{\frac{p-1}{2}}\bmod p - \end{align*} - \vspace{-0.05cm} - \sourcecode{math/legendre.cpp} -\end{algorithm} - -\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 entsprechenden multiplikativen Funktion}{1} - - \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} 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 - \item $\mu(n)=0$, falls $n$ nicht quadratfrei ist - \end{itemize} - - \textbf{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion:} - \begin{itemize} - \item Zählt die relativ primen Zahlen $\leq n$. - \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}$. - Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}: - $a^{m} \equiv a \pmod{m}$ - \end{itemize} -\end{algorithm} - -\begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}} - \begin{itemize} - \item Bis $10^8$ in unter 64MB Speicher (lange Berechnung) - \end{itemize} - \begin{methods} - \method{primeSieve}{berechnet Primzahlen und Anzahl}{N\*\log(\log(N))} - \method{isPrime}{prüft ob Zahl prim ist}{1} - \end{methods} - \sourcecode{math/primeSieve.cpp} -\end{algorithm} - -\begin{algorithm}{\textsc{Möbius}-Inversion} - \begin{itemize} - \item Seien $f,g : \mathbb{N} \to \mathbb{N}$ und $g(n) := \sum_{d \vert n}f(d)$. - Dann ist $f(n) = \sum_{d \vert n}g(d)\mu(\frac{n}{d})$. - \item $\sum\limits_{d \vert n}\mu(d) = - \begin{cases*} - 1 & falls $n = 1$\\ - 0 & sonst - \end{cases*}$ - \end{itemize} - \textbf{Beispiel Inklusion/Exklusion:} - Gegeben sein eine Sequenz $A={a_1,\ldots,a_n}$ von Zahlen, $1 \leq a_i \leq N$. Zähle die Anzahl der \emph{coprime subsequences}.\newline - \textbf{Lösung}: - Für jedes $x$, sei $cnt[x]$ die Anzahl der Vielfachen von $x$ in $A$. - Es gibt $2^{[x]}-1$ nicht leere Subsequences in $A$, die nur Vielfache von $x$ enthalten. - Die Anzahl der Subsequences mit $\ggT=1$ ist gegeben durch $\sum_{i = 1}^N \mu(i) \cdot (2^{cnt[i]} - 1)$. -\end{algorithm} - -\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$} -\method{gauss}{löst LGS}{n^3} -\sourcecode{math/lgsFp.cpp} - -\subsection{LGS über $\boldsymbol{\mathbb{R}}$} -\method{gauss}{löst LGS}{n^3} -\sourcecode{math/gauss.cpp} - -\begin{algorithm}{Inversionszahl} - \vspace{-2pt} - \sourcecode{math/inversions.cpp} -\end{algorithm} - -\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} - \label{fft} - Multipliziert Polynome $A$ und $B$. - \ifthenelse{\isundefined{\srclink}}{}{% - \hfill - \begin{ocg}[printocg=never]{Source links}{srclinks}{1}% - \href{\srclink{math/transforms/}}{\faExternalLink}% - \end{ocg}% - } - \begin{itemize} - \item $\deg(A \cdot B) = \deg(A) + \deg(B)$ - \item Vektoren \code{a} und \code{b} müssen mindestens Größe - $\deg(A \cdot B) + 1$ haben. - Größe muss eine Zweierpotenz sein. - \item Für ganzzahlige Koeffizienten: \code{(ll)round(real(a[i]))} - \item \emph{or} Transform berechnet sum over subsets - $\rightarrow$ inverse für inclusion/exclusion - \end{itemize} - \sourcecode{math/transforms/fft.cpp} - \sourcecode{math/transforms/ntt.cpp} - \sourcecode{math/transforms/bitwiseTransforms.cpp} - Multiplikation mit 2 Transforms statt 3: (nur benutzen wenn nötig!) - \sourcecode{math/transforms/fftMul.cpp} -\end{algorithm} - -\begin{algorithm}{Operations on Formal Power Series} - \sourcecode{math/transforms/seriesOperations.cpp} -\end{algorithm} - -\subsection{Kombinatorik} - -\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\}$) -\begin{align*} - (n-1)!\equiv\begin{cases} - -1\bmod{n},&\mathrm{falls}~n \in \mathbb{P}\\ - \hphantom{-}2\bmod{n},&\mathrm{falls}~n = 4\\ - \hphantom{-}0\bmod{n},&\mathrm{sonst} - \end{cases} -\end{align*} - -\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}'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} -\[ - \binom{m}{n} \equiv \prod_{i=0}^k\binom{m_i}{n_i} \bmod{p}. -\] - -%\begin{algorithm}{Binomialkoeffizienten} -\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{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$ - - \begin{methods} - \method{binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k} - \end{methods} - \sourcecode{math/binomial1.cpp} - - \optional{ - \begin{methods} - \method{binom}{berechnet Primfaktoren vom Binomialkoeffizient}{n\*\log(n)} - \end{methods} - \opthint \\ - \textbf{WICHTIG:} braucht alle Primzahlen $\leq n$ - \sourcecode{math/binomial2.cpp} - } - - \begin{methods} - \method{binom}{berechnet Binomialkoeffizient modulo Primzahl $p$}{p-n} - \end{methods} - \sourcecode{math/binomial3.cpp} -%\end{algorithm} - -\paragraph{\textsc{Catalan}-Zahlen:} -$1,~1,~2,~5,~14,~42,~132,~429,~1430,~4862,~16796,~58786,~208012,~742900$ -\begin{itemize} - \item Die \textsc{Catalan}-Zahl $C_n$ gibt an: - \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 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} -\end{itemize} -\[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{4n - 2}{n+1} C_{n-1} \sim \frac{4^n}{n^{3/2} \sqrt{\pi}}\] -\begin{itemize} - \item Formel $1$ ohne Division in \runtime{n^2}, Formel $2$ und $3$ in \runtime{n} -\end{itemize} - -\paragraph{\textsc{Catalan}-Convolution} -\begin{itemize} - \item Anzahl an Klammerausdrücken mit $n+k$ Klammerpaaren, die mit $\texttt{(}^k$ beginnen. -\end{itemize} -\[C^k_0 = 1\qquad C^k_n = \sum\limits_{\mathclap{a_0+a_1+\dots+a_k=n}} C_{a_0}C_{a_1}\cdots C_{a_k} = -\frac{k+1}{n+k+1}\binom{2n+k}{n} = \frac{(2n+k-1)(2n+k)}{n(n+k+1)} C_{n-1}\] - -\paragraph{\textsc{Euler}-Zahlen:} -$|~1~|~1~|~1,~1~|~1,~4,~1~|~1,~11,~11,~1~|~1,~26,~66,~26,~1~|$ - -Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Anstiegen. -Für die $n$-te Zahl gibt es $n$ mögliche Positionen zum Einfügen. -Dabei wird entweder ein Anstieg in zwei gesplitted oder ein Anstieg um $n$ ergänzt. -\[\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \quad -\eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1}\] -\[ -\eulerI{n}{k} = [x^k] - \left(\sum_{i=0}^\infty (i+1)^n x^i\right) - \left(\sum_{i=0}^\infty (-1)^i \binom{n+1}{i} x^i\right) -\] - -\paragraph{\textsc{Stirling}-Zahlen 1. Art:} -$|~1~|~0,~1~|~0,~1,~1~|~0,~2,~3,~1~|~0,~6,~11,~6,~1~|$ - -Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Zyklen. -Es gibt zwei Möglichkeiten für die $n$-te Zahl. Entweder sie bildet einen eigenen Zyklus, oder sie kann an jeder Position in jedem Zyklus einsortiert werden. -\[\stirlingI{0}{0} = 1 \qquad -\stirlingI{n}{0} = \stirlingI{0}{k} = 0 \qquad -\stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}\] -\[ -\stirlingI{n}{k} -= [x^k]\prod_{i=0}^{n-1} (x+i) -= n! [x^{n-k}] \frac{1}{k!} \left(\sum_{i=0}^\infty \frac{1}{i+1}x^i\right)^k -\] - -\paragraph{\textsc{Stirling}-Zahlen 2. Art:} -$|~1~|~0,~1~|~0,~1,~1~|~0,~1,~3,~1~|~0,~1,~7,~6,~1~|$ - -Die Anzahl der Möglichkeiten $n$ Elemente in $k$ nichtleere Teilmengen zu zerlegen. -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. -\[\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad -\stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1} -\] -\[ -\stirlingII{n}{k} -= [x^k] - \left(\sum_{i=0}^\infty \frac{i^n}{i!}x^i\right) - \left(\sum_{i=0}^\infty \frac{(-1)^i}{i!}x^i\right) -= n! [x^{n-k}] \frac{1}{k!} \left(\sum_{i=0}^\infty \frac{1}{(i+1)!}x^i\right)^k -\] - -\paragraph{\textsc{Bell}-Zahlen:} -$1,~1,~2,~5,~15,~52,~203,~877,~4140,~21147,~115975,~678570,~4213597$ - -Anzahl der Partitionen von $\{1, \ldots, n\}$. -Wie \textsc{Stirling}-Zahlen 2. Art ohne Limit durch $k$. -\[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} -= n! [x^n] e^{e^x-1} -\qquad -B_{p^m+n}\equiv m\cdot B_n + B_{n+1} \bmod{p}\] - -\paragraph{$\boldsymbol{k}$ Partitions:} -$|~1~|~0,~1~|~0,~1,~1~|~0,~1,~1,~1~|~0,~1,~2,~1,~1~|~0,~1,~2,~2,~1,~1~|~0,~1,~3,~3,~2,~1,~1~|$ - -Die Anzahl der Partitionen von $n$ in genau $k$ positive Summanden. -Die Anzahl der Partitionen von $n$ mit größtem Elementen $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)\\ -\end{align*} - -\paragraph{Partitions:} -$1,~1,~2,~3,~5,~7,~11,~15,~22,~30,~42,~56,~77,~101,~135,~176,~231,~297,~385,~490,~627$ - -\begin{align*} - 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] \\ - p(n)&=[x^n] \left(\sum_{k=-\infty}^\infty (-1)^k x^{k(3k-1)/2}\right)^{-1} - \sim \frac{1}{4 \sqrt{3} n} \exp\left(\pi \sqrt{\frac{2n}{3}}\right) -\end{align*} -\begin{itemize} - \item in Formel $3$ kann abgebrochen werden wenn $\frac{k(3k-1)}{2} > n$. - $\rightarrow$ \runtime{n \sqrt{n}} - \item Die Anzahl der Partitionen von $n$ in bis zu $k$ positive Summanden ist $\sum\limits_{i=0}^{k}p_i(n)=p_k(n+k)$. -\end{itemize} - -\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/prime-composite} - -\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ } -\method{recover}{findet $x$ und $y$ für $c=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} - \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} - -\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$} -\sourcecode{math/piLegendre.cpp} -} - -\begin{algorithm}[optional]{Big Integers} - \sourcecode{math/bigint.cpp} -\end{algorithm} +\section{Mathe} + +\begin{algorithm}{Longest Increasing Subsequence} + \begin{itemize} + \item \code{lower\_bound} $\Rightarrow$ streng monoton + \item \code{upper\_bound} $\Rightarrow$ monoton + \end{itemize} + \sourcecode{math/longestIncreasingSubsequence.cpp} +\end{algorithm} +\columnbreak + +\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} +\columnbreak + +\subsection{Potenzen in $\boldsymbol{\mathbb{Z}/n\mathbb{Z}}$} + \begin{methods} + \method{powMod}{berechnet $a^b \bmod n$}{\log(b)} + \end{methods} + \sourcecode{math/modPowIterativ.cpp} + \begin{itemize} + \item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten! + \end{itemize} + +\optional{ +\subsection{Multiplikation in $\boldsymbol{\mathbb{Z}/n\mathbb{Z}}$ \opthint} + \begin{methods} + \method{mulMod}{berechnet $a \cdot b \bmod n$}{\log(b)} + \end{methods} + \sourcecode{math/modMulIterativ.cpp} +} + +\begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus} + \runtime{\log(a) + \log(b)} + \sourcecode{math/extendedEuclid.cpp} +\end{algorithm} + +\subsection{Multiplikatives Inverses von $\boldsymbol{x}$ in $\boldsymbol{\mathbb{Z}/m\mathbb{Z}}$} +\textbf{Falls $\boldsymbol{m}$ prim:}\quad $x^{-1} \equiv x^{m-2} \bmod m$ + +\textbf{Falls $\boldsymbol{\ggT(x, m) = 1}$:} +\begin{itemize} + \item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit + $\alpha x + \beta m = 1$. + \item Nach Kongruenz gilt $\alpha x + \beta m \equiv \alpha x \equiv 1 \bmod m$. + \item $x^{-1} :\equiv \alpha \bmod m$ +\end{itemize} +\textbf{Sonst $\boldsymbol{\ggT(x, m) > 1}$:}\quad Es existiert kein $x^{-1}$. +% \sourcecode{math/multInv.cpp} +\sourcecode{math/shortModInv.cpp} + +\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: +\[ +\left(x + k\frac{b}{\ggT(a, b)},~y - k\frac{a}{\ggT(a, b)}\right) +\] + +\paragraph{\textsc{Pell}-Gleichungen} +Sei $(\overline{x}, \overline{y})$ die Lösung von $x^2 - ny^2 = 1$, die $x>1$ minimiert. +Sei $(\tilde{x}, \tilde{y})$ die Lösung von $x^2-ny^2 = c$, die $x>1$ minimiert. Dann lassen +sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: +\begin{align*} + x_1&\coloneqq \tilde{x}, & y_1&\coloneqq\tilde{y}\\ + 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}{Lineare Kongruenz} + \begin{itemize} + \item Kleinste Lösung $x$ für $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} + \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 \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 + \] + Formel kann auch für nicht teilerfremde Moduli verwendet werden. + Sind die Moduli nicht teilerfremd, existiert genau dann eine Lösung, + wenn $a\equiv~b \bmod \ggT(m, n)$. + In diesem Fall sind keine Faktoren + auf der linken Seite erlaubt. + \end{itemize} + \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} +\end{algorithm} + +\begin{algorithm}{Teiler} + \begin{methods} + \method{countDivisors}{Zählt Teiler von $n$}{\sqrt[\leftroot{3}\uproot{2}3]{n}} + \end{methods} + \sourcecode{math/divisors.cpp} +\end{algorithm} + +\begin{algorithm}{Matrix-Exponent} + \begin{methods} + \method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3} + \method{calc}{berechnet $m^b \cdot v$}{\log(b)\cdot n^2} + \end{methods} + \textbf{Tipp:} wenn \code{v[x]=1} und \code{0} sonst, dann ist \code{res[y]} = $m^b_{y,x}$. + \sourcecode{math/matrixPower.cpp} +\end{algorithm} + +\begin{algorithm}{Lineare Rekurrenz} + \begin{methods} + \method{BerlekampMassey}{Berechnet eine lineare Rekurrenz $n$-ter Ordnung}{n^2} + \method{}{aus den ersten $2n$ Werte}{} + \end{methods} + \sourcecode{math/berlekampMassey.cpp} + 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 \text{mul}(n)} + \end{methods} + 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} + \begin{pmatrix} + c_{0} & c_{1} & \smash{\cdots} & \smash{\cdots} & c_{n-1} \\ + 1 & 0 & \smash{\cdots} & \smash{\cdots} & 0 \\ + 0 & \smash{\ddots} & \smash{\ddots} & & \smash{\vdots} \\ + \smash{\vdots} & \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}{Diskreter Logarithmus} + \begin{methods} + \method{solve}{bestimmt Lösung $x$ für $a^x=b \bmod m$}{\sqrt{m}\*\log(m)} + \end{methods} + \sourcecode{math/discreteLogarithm.cpp} +\end{algorithm} + +\begin{algorithm}{Diskrete Quadratwurzel} + \begin{methods} + \method{sqrtMod}{bestimmt Lösung $x$ für $x^2=a \bmod p$ }{\log(p)} + \end{methods} + \textbf{Wichtig:} $p$ muss prim sein! + \sourcecode{math/sqrtModCipolla.cpp} +\end{algorithm} +%\columnbreak + +\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}\}$ + \item es existiert entweder keine oder $\varphi(\varphi(n))$ inkongruente Primitivwurzeln + \item Sei $g$ Primitivwurzel modulo $n$. + Dann gilt:\newline + Das kleinste $k$, sodass $g^k \equiv 1 \bmod n$, ist $k = \varphi(n)$. + \end{itemize} + \begin{methods} + \method{isPrimitive}{prüft ob $g$ eine Primitivwurzel ist}{\log(\varphi(n))\*\log(n)} + \method{findPrimitive}{findet Primitivwurzel (oder -1)}{\abs{ans}\*\log(\varphi(n))\*\log(n)} + \end{methods} + \sourcecode{math/primitiveRoot.cpp} +\end{algorithm} + +\begin{algorithm}{Diskrete \textrm{\textit{n}}-te Wurzel} + \begin{methods} + \method{root}{bestimmt Lösung $x$ für $x^a=b \bmod m$ }{\sqrt{m}\*\log(m)} + \end{methods} + Alle Lösungen haben die Form $g^{c + \frac{i \cdot \phi(n)}{\gcd(a, \phi(n))}}$ + \sourcecode{math/discreteNthRoot.cpp} +\end{algorithm} + +\begin{algorithm}{\textsc{Legendre}-Symbol} + Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$: + \vspace{-0.15cm}\begin{align*} + \hspace*{3cm}\legendre{a}{p} &= + \begin{cases*} + \hphantom{-}0 & falls $p~\vert~a$ \\[-1ex] + \hphantom{-}1 & falls $\exists x \in \mathbb{Z}\backslash p\mathbb{Z} : a \equiv x^2 \bmod p$ \\[-1ex] + -1 & sonst + \end{cases*} \\ + \legendre{-1}{p} = (-1)^{\frac{p - 1}{2}} &= + \begin{cases*} + \hphantom{-}1 & falls $p \equiv 1 \bmod 4$ \\[-1ex] + -1 & falls $p \equiv 3 \bmod 4$ + \end{cases*} \\ + \legendre{2}{p} = (-1)^{\frac{p^2 - 1}{8}} &= + \begin{cases*} + \hphantom{-}1 & falls $p \equiv \pm 1 \bmod 8$ \\[-1ex] + -1 & falls $p \equiv \pm 3 \bmod 8$ + \end{cases*} + \end{align*} + \begin{align*} + \legendre{p}{q} \cdot \legendre{q}{p} = (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} && + \legendre{a}{p} \equiv a^{\frac{p-1}{2}}\bmod p + \end{align*} + \vspace{-0.05cm} + \sourcecode{math/legendre.cpp} +\end{algorithm} + +\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 entsprechenden multiplikativen Funktion}{1} + + \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} 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 + \item $\mu(n)=0$, falls $n$ nicht quadratfrei ist + \end{itemize} + + \textbf{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion:} + \begin{itemize} + \item Zählt die relativ primen Zahlen $\leq n$. + \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}$. + Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}: + $a^{m} \equiv a \pmod{m}$ + \end{itemize} +\end{algorithm} + +\begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}} + \begin{itemize} + \item Bis $10^8$ in unter 64MB Speicher (lange Berechnung) + \end{itemize} + \begin{methods} + \method{primeSieve}{berechnet Primzahlen und Anzahl}{N\*\log(\log(N))} + \method{isPrime}{prüft ob Zahl prim ist}{1} + \end{methods} + \sourcecode{math/primeSieve.cpp} +\end{algorithm} + +\begin{algorithm}{\textsc{Möbius}-Inversion} + \begin{itemize} + \item Seien $f,g : \mathbb{N} \to \mathbb{N}$ und $g(n) := \sum_{d \vert n}f(d)$. + Dann ist $f(n) = \sum_{d \vert n}g(d)\mu(\frac{n}{d})$. + \item $\sum\limits_{d \vert n}\mu(d) = + \begin{cases*} + 1 & falls $n = 1$\\ + 0 & sonst + \end{cases*}$ + \end{itemize} + \textbf{Beispiel Inklusion/Exklusion:} + Gegeben sein eine Sequenz $A={a_1,\ldots,a_n}$ von Zahlen, $1 \leq a_i \leq N$. Zähle die Anzahl der \emph{coprime subsequences}.\newline + \textbf{Lösung}: + Für jedes $x$, sei $cnt[x]$ die Anzahl der Vielfachen von $x$ in $A$. + Es gibt $2^{[x]}-1$ nicht leere Subsequences in $A$, die nur Vielfache von $x$ enthalten. + Die Anzahl der Subsequences mit $\ggT=1$ ist gegeben durch $\sum_{i = 1}^N \mu(i) \cdot (2^{cnt[i]} - 1)$. +\end{algorithm} + +\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$} +\method{gauss}{löst LGS}{n^3} +\sourcecode{math/lgsFp.cpp} + +\subsection{LGS über $\boldsymbol{\mathbb{R}}$} +\method{gauss}{löst LGS}{n^3} +\sourcecode{math/gauss.cpp} + +\begin{algorithm}{Inversionszahl} + \vspace{-2pt} + \sourcecode{math/inversions.cpp} +\end{algorithm} + +\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} + \label{fft} + Multipliziert Polynome $A$ und $B$. + \ifthenelse{\isundefined{\srclink}}{}{% + \hfill + \begin{ocg}[printocg=never]{Source links}{srclinks}{1}% + \href{\srclink{math/transforms/}}{\faExternalLink}% + \end{ocg}% + } + \begin{itemize} + \item $\deg(A \cdot B) = \deg(A) + \deg(B)$ + \item Vektoren \code{a} und \code{b} müssen mindestens Größe + $\deg(A \cdot B) + 1$ haben. + Größe muss eine Zweierpotenz sein. + \item Für ganzzahlige Koeffizienten: \code{(ll)round(real(a[i]))} + \item \emph{or} Transform berechnet sum over subsets + $\rightarrow$ inverse für inclusion/exclusion + \end{itemize} + \sourcecode{math/transforms/fft.cpp} + \sourcecode{math/transforms/ntt.cpp} + \sourcecode{math/transforms/bitwiseTransforms.cpp} + Multiplikation mit 2 Transforms statt 3: (nur benutzen wenn nötig!) + \sourcecode{math/transforms/fftMul.cpp} +\end{algorithm} + +\begin{algorithm}{Operations on Formal Power Series} + \sourcecode{math/transforms/seriesOperations.cpp} +\end{algorithm} + +\subsection{Kombinatorik} + +\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\}$) +\begin{align*} + (n-1)!\equiv\begin{cases} + -1\bmod{n},&\mathrm{falls}~n \in \mathbb{P}\\ + \hphantom{-}2\bmod{n},&\mathrm{falls}~n = 4\\ + \hphantom{-}0\bmod{n},&\mathrm{sonst} + \end{cases} +\end{align*} + +\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}'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} +\[ + \binom{m}{n} \equiv \prod_{i=0}^k\binom{m_i}{n_i} \bmod{p}. +\] + +%\begin{algorithm}{Binomialkoeffizienten} +\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{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$ + + \begin{methods} + \method{binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k} + \end{methods} + \sourcecode{math/binomial1.cpp} + + \optional{ + \begin{methods} + \method{binom}{berechnet Primfaktoren vom Binomialkoeffizient}{n\*\log(n)} + \end{methods} + \opthint \\ + \textbf{WICHTIG:} braucht alle Primzahlen $\leq n$ + \sourcecode{math/binomial2.cpp} + } + + \begin{methods} + \method{binom}{berechnet Binomialkoeffizient modulo Primzahl $p$}{p-n} + \end{methods} + \sourcecode{math/binomial3.cpp} +%\end{algorithm} + +\paragraph{\textsc{Catalan}-Zahlen:} +$1,~1,~2,~5,~14,~42,~132,~429,~1430,~4862,~16796,~58786,~208012,~742900$ +\begin{itemize} + \item Die \textsc{Catalan}-Zahl $C_n$ gibt an: + \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 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} +\end{itemize} +\[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{4n - 2}{n+1} C_{n-1} \sim \frac{4^n}{n^{3/2} \sqrt{\pi}}\] +\begin{itemize} + \item Formel $1$ ohne Division in \runtime{n^2}, Formel $2$ und $3$ in \runtime{n} +\end{itemize} + +\paragraph{\textsc{Catalan}-Convolution} +\begin{itemize} + \item Anzahl an Klammerausdrücken mit $n+k$ Klammerpaaren, die mit $\texttt{(}^k$ beginnen. +\end{itemize} +\[C^k_0 = 1\qquad C^k_n = \sum\limits_{\mathclap{a_0+a_1+\dots+a_k=n}} C_{a_0}C_{a_1}\cdots C_{a_k} = +\frac{k+1}{n+k+1}\binom{2n+k}{n} = \frac{(2n+k-1)(2n+k)}{n(n+k+1)} C_{n-1}\] + +\paragraph{\textsc{Euler}-Zahlen:} +$|~1~|~1~|~1,~1~|~1,~4,~1~|~1,~11,~11,~1~|~1,~26,~66,~26,~1~|$ + +Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Anstiegen. +Für die $n$-te Zahl gibt es $n$ mögliche Positionen zum Einfügen. +Dabei wird entweder ein Anstieg in zwei gesplitted oder ein Anstieg um $n$ ergänzt. +\[\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \quad +\eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1}\] +\[ +\eulerI{n}{k} = [x^k] + \left(\sum_{i=0}^\infty (i+1)^n x^i\right) + \left(\sum_{i=0}^\infty (-1)^i \binom{n+1}{i} x^i\right) +\] + +\paragraph{\textsc{Stirling}-Zahlen 1. Art:} +$|~1~|~0,~1~|~0,~1,~1~|~0,~2,~3,~1~|~0,~6,~11,~6,~1~|$ + +Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Zyklen. +Es gibt zwei Möglichkeiten für die $n$-te Zahl. Entweder sie bildet einen eigenen Zyklus, oder sie kann an jeder Position in jedem Zyklus einsortiert werden. +\[\stirlingI{0}{0} = 1 \qquad +\stirlingI{n}{0} = \stirlingI{0}{k} = 0 \qquad +\stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}\] +\[ +\stirlingI{n}{k} += [x^k]\prod_{i=0}^{n-1} (x+i) += n! [x^{n-k}] \frac{1}{k!} \left(\sum_{i=0}^\infty \frac{1}{i+1}x^i\right)^k +\] + +\paragraph{\textsc{Stirling}-Zahlen 2. Art:} +$|~1~|~0,~1~|~0,~1,~1~|~0,~1,~3,~1~|~0,~1,~7,~6,~1~|$ + +Die Anzahl der Möglichkeiten $n$ Elemente in $k$ nichtleere Teilmengen zu zerlegen. +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. +\[\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad +\stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1} +\] +\[ +\stirlingII{n}{k} += [x^k] + \left(\sum_{i=0}^\infty \frac{i^n}{i!}x^i\right) + \left(\sum_{i=0}^\infty \frac{(-1)^i}{i!}x^i\right) += n! [x^{n-k}] \frac{1}{k!} \left(\sum_{i=0}^\infty \frac{1}{(i+1)!}x^i\right)^k +\] + +\paragraph{\textsc{Bell}-Zahlen:} +$1,~1,~2,~5,~15,~52,~203,~877,~4140,~21147,~115975,~678570,~4213597$ + +Anzahl der Partitionen von $\{1, \ldots, n\}$. +Wie \textsc{Stirling}-Zahlen 2. Art ohne Limit durch $k$. +\[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} += n! [x^n] e^{e^x-1} +\qquad +B_{p^m+n}\equiv m\cdot B_n + B_{n+1} \bmod{p}\] + +\paragraph{$\boldsymbol{k}$ Partitions:} +$|~1~|~0,~1~|~0,~1,~1~|~0,~1,~1,~1~|~0,~1,~2,~1,~1~|~0,~1,~2,~2,~1,~1~|~0,~1,~3,~3,~2,~1,~1~|$ + +Die Anzahl der Partitionen von $n$ in genau $k$ positive Summanden. +Die Anzahl der Partitionen von $n$ mit größtem Elementen $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)\\ +\end{align*} + +\paragraph{Partitions:} +$1,~1,~2,~3,~5,~7,~11,~15,~22,~30,~42,~56,~77,~101,~135,~176,~231,~297,~385,~490,~627$ + +\begin{align*} + 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] \\ + p(n)&=[x^n] \left(\sum_{k=-\infty}^\infty (-1)^k x^{k(3k-1)/2}\right)^{-1} + \sim \frac{1}{4 \sqrt{3} n} \exp\left(\pi \sqrt{\frac{2n}{3}}\right) +\end{align*} +\begin{itemize} + \item in Formel $3$ kann abgebrochen werden wenn $\frac{k(3k-1)}{2} > n$. + $\rightarrow$ \runtime{n \sqrt{n}} + \item Die Anzahl der Partitionen von $n$ in bis zu $k$ positive Summanden ist $\sum\limits_{i=0}^{k}p_i(n)=p_k(n+k)$. +\end{itemize} + +\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/prime-composite} + +\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ } +\method{recover}{findet $x$ und $y$ für $c=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} + \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} + +\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$} +\sourcecode{math/piLegendre.cpp} +} + +\begin{algorithm}[optional]{Big Integers} + \sourcecode{math/bigint.cpp} +\end{algorithm} diff --git a/content/math/piLehmer.cpp b/content/math/piLehmer.cpp index adef16d..83e1b95 100644 --- a/content/math/piLehmer.cpp +++ b/content/math/piLehmer.cpp @@ -1,52 +1,52 @@ -constexpr ll cacheA = 2 * 3 * 5 * 7 * 11 * 13 * 17; -constexpr ll cacheB = 7; -ll memoA[cacheA + 1][cacheB + 1]; -ll memoB[cacheB + 1]; -ll memoC[N]; - -void init() { - primeSieve(); // @\sourceref{math/primeSieve.cpp}@ - for (ll i = 1; i < N; i++) { - memoC[i] = memoC[i - 1]; - if (isPrime(i)) memoC[i]++; - } - memoB[0] = 1; - for(ll i = 0; i <= cacheA; i++) memoA[i][0] = i; - for(ll i = 1; i <= cacheB; i++) { - memoB[i] = primes[i - 1] * memoB[i - 1]; - for(ll j = 1; j <= cacheA; j++) { - memoA[j][i] = memoA[j][i - 1] - memoA[j / - primes[i - 1]][i - 1]; -}}} - -ll phi(ll n, ll k) { - if(k == 0) return n; - if(k <= cacheB) - return memoA[n % memoB[k]][k] + - (n / memoB[k]) * memoA[memoB[k]][k]; - if(n <= primes[k - 1]*primes[k - 1]) return memoC[n] - k + 1; - if(n <= primes[k - 1]*primes[k - 1]*primes[k - 1] && n < N) { - ll b = memoC[(ll)sqrtl(n)]; - ll res = memoC[n] - (b + k - 2) * (b - k + 1) / 2; - for(ll i = k; i < b; i++) res += memoC[n / primes[i]]; - return res; - } - return phi(n, k - 1) - phi(n / primes[k - 1], k - 1); -} - -ll pi(ll n) { - if (n < N) return memoC[n]; - ll a = pi(sqrtl(sqrtl(n))); - ll b = pi(sqrtl(n)); - ll c = pi(cbrtl(n)); - ll res = phi(n, a) + (b + a - 2) * (b - a + 1) / 2; - for (ll i = a; i < b; i++) { - ll w = n / primes[i]; - res -= pi(w); - if (i > c) continue; - ll bi = pi(sqrtl(w)); - for (ll j = i; j < bi; j++) { - res -= pi(w / primes[j]) - j; - }} - return res; -} +constexpr ll cacheA = 2 * 3 * 5 * 7 * 11 * 13 * 17; +constexpr ll cacheB = 7; +ll memoA[cacheA + 1][cacheB + 1]; +ll memoB[cacheB + 1]; +ll memoC[N]; + +void init() { + primeSieve(); // @\sourceref{math/primeSieve.cpp}@ + for (ll i = 1; i < N; i++) { + memoC[i] = memoC[i - 1]; + if (isPrime(i)) memoC[i]++; + } + memoB[0] = 1; + for(ll i = 0; i <= cacheA; i++) memoA[i][0] = i; + for(ll i = 1; i <= cacheB; i++) { + memoB[i] = primes[i - 1] * memoB[i - 1]; + for(ll j = 1; j <= cacheA; j++) { + memoA[j][i] = memoA[j][i - 1] - memoA[j / + primes[i - 1]][i - 1]; +}}} + +ll phi(ll n, ll k) { + if(k == 0) return n; + if(k <= cacheB) + return memoA[n % memoB[k]][k] + + (n / memoB[k]) * memoA[memoB[k]][k]; + if(n <= primes[k - 1]*primes[k - 1]) return memoC[n] - k + 1; + if(n <= primes[k - 1]*primes[k - 1]*primes[k - 1] && n < N) { + ll b = memoC[(ll)sqrtl(n)]; + ll res = memoC[n] - (b + k - 2) * (b - k + 1) / 2; + for(ll i = k; i < b; i++) res += memoC[n / primes[i]]; + return res; + } + return phi(n, k - 1) - phi(n / primes[k - 1], k - 1); +} + +ll pi(ll n) { + if (n < N) return memoC[n]; + ll a = pi(sqrtl(sqrtl(n))); + ll b = pi(sqrtl(n)); + ll c = pi(cbrtl(n)); + ll res = phi(n, a) + (b + a - 2) * (b - a + 1) / 2; + for (ll i = a; i < b; i++) { + ll w = n / primes[i]; + res -= pi(w); + if (i > c) continue; + ll bi = pi(sqrtl(w)); + for (ll j = i; j < bi; j++) { + res -= pi(w / primes[j]) - j; + }} + return res; +} -- cgit v1.2.3