diff options
Diffstat (limited to 'content/math')
| -rw-r--r-- | content/math/binomial0.cpp | 2 | ||||
| -rw-r--r-- | content/math/math.tex | 20 | ||||
| -rw-r--r-- | content/math/tables/composite.tex | 26 | ||||
| -rw-r--r-- | content/math/tables/prime-composite.tex | 31 |
4 files changed, 42 insertions, 37 deletions
diff --git a/content/math/binomial0.cpp b/content/math/binomial0.cpp index 5f2ccaa..f37aea5 100644 --- a/content/math/binomial0.cpp +++ b/content/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[k] * inv[n-k] % mod) * fac[n] % mod; + return (fac[n] * inv[n-k] % mod) * inv[k] % mod; } diff --git a/content/math/math.tex b/content/math/math.tex index 4ac6c9e..644fbc8 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -26,7 +26,7 @@ \end{methods}
\sourcecode{math/permIndex.cpp}
\end{algorithm}
-\clearpage
+\columnbreak
\subsection{Mod-Exponent und Multiplikation über $\boldsymbol{\mathbb{F}_p}$}
%\vspace{-1.25em}
@@ -100,8 +100,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}
@@ -236,7 +236,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 +250,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 +263,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}$
@@ -345,7 +345,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 +357,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}
@@ -542,7 +542,7 @@ 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)}
diff --git a/content/math/tables/composite.tex b/content/math/tables/composite.tex deleted file mode 100644 index 7a6ab09..0000000 --- a/content/math/tables/composite.tex +++ /dev/null @@ -1,26 +0,0 @@ -\begin{expandtable} -\begin{tabularx}{\linewidth}{|r||r|R||r||r|} - \hline - $10^x$ & Highly Composite & \# Divs & \# prime Divs & \# Primes \\ - \hline - 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/prime-composite.tex b/content/math/tables/prime-composite.tex new file mode 100644 index 0000000..073b4ba --- /dev/null +++ b/content/math/tables/prime-composite.tex @@ -0,0 +1,31 @@ +\begin{expandtable} +\begin{tabularx}{\linewidth}{|r|rIr|rIr|r|r|} + \hline + \multirow{2}{*}{$10^x$} + & \multirow{2}{*}{Highly Composite} + & \multirow{2}{*}{\# Divs} + & \multicolumn{2}{|c|}{Prime} + & \multirow{2}{*}{\# Primes} & \multirow{2}{*}{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 \\ + \hline +\end{tabularx} +\end{expandtable} |