diff options
Diffstat (limited to 'content/math/math.tex')
| -rw-r--r-- | content/math/math.tex | 86 |
1 files changed, 49 insertions, 37 deletions
diff --git a/content/math/math.tex b/content/math/math.tex index 4ac6c9e..f1eec86 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -26,21 +26,24 @@ \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}
-\method{mulMod}{berechnet $a \cdot b \bmod n$}{\log(b)}
-\sourcecode{math/modMulIterativ.cpp}
-% \vfill\null\columnbreak
-\method{powMod}{berechnet $a^b \bmod n$}{\log(b)}
-\sourcecode{math/modPowIterativ.cpp}
-%\end{multicols}
-%\vspace{-2.75em}
-\begin{itemize}
- \item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten!
-\end{itemize}
+\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)}
@@ -100,8 +103,8 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: 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{itemize}
+ \sourcecode{math/chineseRemainder.cpp}
\end{algorithm}
\begin{algorithm}{Primzahltest \& Faktorisierung}
@@ -121,7 +124,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \begin{algorithm}{Matrix-Exponent}
\begin{methods}
\method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3}
- \method{calc}{berechnet $m^b\cdot$}{\log(b)\cdot n^2}
+ \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}
@@ -236,7 +239,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/legendre.cpp}
\end{algorithm}
-\begin{algorithm}{Lineares Sieb 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.
@@ -250,7 +253,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \textbf{Wichtig:} Sieb rechts ist schneller für \code{isPrime} oder \code{primes}!
\sourcecode{math/linearSieve.cpp}
- \textbf{\textsc{Möbius}-Funktion:}
+ \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
@@ -263,7 +266,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}$
@@ -321,21 +324,27 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \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{xor}, \emph{or} und \emph{and} Transform funktioniert auch mit \code{double} oder modulo einer Primzahl $p$ falls $p \geq 2^{\texttt{bits}}$
+ \item \emph{or} Transform berechnet sum over subsets
+ $\rightarrow$ inverse für inclusion/exclusion
\end{itemize}
- %\sourcecode{math/fft.cpp}
- %\sourcecode{math/ntt.cpp}
\sourcecode{math/transforms/fft.cpp}
\sourcecode{math/transforms/ntt.cpp}
\sourcecode{math/transforms/bitwiseTransforms.cpp}
- Multiplikation mit 2 transforms statt 3: (nur benutzten wenn nötig!)
+ Multiplikation mit 2 Transforms statt 3: (nur benutzen wenn nötig!)
\sourcecode{math/transforms/fftMul.cpp}
\end{algorithm}
@@ -345,7 +354,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \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\}$)
@@ -357,14 +366,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}
@@ -390,16 +399,19 @@ so gilt \end{methods}
\sourcecode{math/binomial1.cpp}
+ \optional{
+ \begin{methods}
+ \method{calc\_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{calc\_binom}{berechnet Binomialkoeffizient modulo Primzahl $p$}{p-n}
\end{methods}
\sourcecode{math/binomial3.cpp}
-
-% \begin{methods}
-% \method{calc\_binom}{berechnet Primfaktoren vom Binomialkoeffizient}{n}
-% \end{methods}
-% \textbf{WICHTIG:} braucht alle Primzahlen $\leq n$
-% \sourcecode{math/binomial2.cpp}
%\end{algorithm}
\paragraph{\textsc{Catalan}-Zahlen}
@@ -542,10 +554,10 @@ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \text \input{math/tables/series}
\subsection{Wichtige Zahlen}
-\input{math/tables/composite}
+\input{math/tables/prime-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)}
+\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}
|