From 36ba8589fa0154d73354bd8e0101213f2d5f9ba4 Mon Sep 17 00:00:00 2001 From: Yidi Date: Fri, 22 Mar 2024 12:21:56 +0100 Subject: reorder to improve spacing --- math/math.tex | 189 +++++++++++++++++++++++++++++----------------------------- 1 file changed, 96 insertions(+), 93 deletions(-) (limited to 'math/math.tex') diff --git a/math/math.tex b/math/math.tex index 8ccc55e..8a30b86 100644 --- a/math/math.tex +++ b/math/math.tex @@ -1,5 +1,12 @@ \section{Mathe} +\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}{Longest Increasing Subsequence} \begin{itemize} \item \code{lower\_bound} $\Rightarrow$ streng monoton @@ -7,14 +14,6 @@ \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} @@ -44,21 +43,20 @@ \begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus} \runtime{\log(a) + \log(b)} - \sourcecode{math/gcd-lcm.cpp} \sourcecode{math/extendedEuclid.cpp} \end{algorithm} -\subsection{Multiplikatives Inverses von $\boldsymbol{n}$ in $\boldsymbol{\mathbb{Z}/p\mathbb{Z}}$} -\textbf{Falls $\boldsymbol{p}$ prim:}\quad $x^{-1} \equiv x^{p-2} \bmod p$ +\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(n, p) = 1}$:} +\textbf{Falls $\boldsymbol{\ggT(x, m) = 1}$:} \begin{itemize} \item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit - $\alpha n + \beta p = 1$. - \item Nach Kongruenz gilt $\alpha n + \beta p \equiv \alpha n \equiv 1 \bmod p$. - \item $n^{-1} :\equiv \alpha \bmod p$ + $\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(n, p) > 1}$:}\quad Es existiert kein $x^{-1}$. +\textbf{Sonst $\boldsymbol{\ggT(x, m) > 1}$:}\quad Es existiert kein $x^{-1}$. % \sourcecode{math/multInv.cpp} \sourcecode{math/shortModInv.cpp} @@ -121,19 +119,12 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/divisors.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}\}$ - \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} +\begin{algorithm}{Numerisch Extremstelle bestimmen} + \sourcecode{math/goldenSectionSearch.cpp} +\end{algorithm} + +\begin{algorithm}{Numerisch Integrieren, Simpsonregel} + \sourcecode{math/simpson.cpp} \end{algorithm} \begin{algorithm}{Diskreter Logarithmus} @@ -151,6 +142,22 @@ 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}\}$ + \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}{Linearessieb 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$. @@ -185,7 +192,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \end{itemize} \end{algorithm} - \begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}} \begin{itemize} \item Bis $10^8$ in unter 64MB Speicher (lange Berechnung) @@ -216,33 +222,25 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: %\sourcecode{math/mobius.cpp} \end{algorithm} -%\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}$. -% 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} - - -\begin{algorithm}{Numerisch Extremstelle bestimmen} - \sourcecode{math/goldenSectionSearch.cpp} -\end{algorithm} - - -\begin{algorithm}{Numerisch Integrieren, Simpsonregel} - \sourcecode{math/simpson.cpp} -\end{algorithm} +\optional{ +\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}$. + 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} +} \begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen} Multipliziert Polynome $A$ und $B$. @@ -259,21 +257,53 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: %\textcolor{safeOrange}{$\blacksquare$} NTT code, %\textcolor{safeGreen}{$\blacksquare$} FFT code \sourcecode{math/transforms/fft.cpp} \sourcecode{math/transforms/ntt.cpp} + \vfill* + \columnbreak \sourcecode{math/transforms/bitwiseTransforms.cpp} Multiplikation mit 2 transforms statt 3: (nur benutzten wenn nötig!) \sourcecode{math/transforms/fftMul.cpp} \end{algorithm} -\subsection{LGS über $\boldsymbol{\mathbb{R}}$} -\method{gauss}{löst LGS}{n^3} -\sourcecode{math/gauss.cpp} +\begin{algorithm}{Operations on Formal Power Series} + \sourcecode{math/transforms/seriesOperations.cpp} +\end{algorithm} \subsection{LGS über $\boldsymbol{\mathbb{F}_p}$} \method{gauss}{löst LGS}{n^3} \sourcecode{math/lgsFp.cpp} -\clearpage +\subsection{LGS über $\boldsymbol{\mathbb{R}}$} +\method{gauss}{löst LGS}{n^3} +\sourcecode{math/gauss.cpp} + +\begin{algorithm}{\textsc{Legendre}-Symbol} + Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$: + \begin{align*} + \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*} + \sourcecode{math/legendre.cpp} +\end{algorithm} +\optional{ \subsection{Primzahlzählfunktion $\boldsymbol{\pi}$} \begin{methods} \method{init}{berechnet $\pi$ bis $N$}{N\*\log(\log(N))} @@ -281,6 +311,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \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} @@ -331,33 +362,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/matrixPower.cpp} \end{algorithm} -\begin{algorithm}{\textsc{Legendre}-Symbol} - Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$: - \begin{align*} - \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*} - \sourcecode{math/legendre.cpp} -\end{algorithm} - \begin{algorithm}{Inversionszahl} \sourcecode{math/inversions.cpp} \end{algorithm} @@ -411,14 +415,13 @@ so gilt \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$ -\columnbreak - - \begin{methods} + + \begin{methods} \method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k} \end{methods} \sourcecode{math/binomial1.cpp} - - \begin{methods} + + \begin{methods} \method{calc\_binom}{berechnet Binomialkoeffizient modulo Primzahl $p$}{p-n} \end{methods} \sourcecode{math/binomial3.cpp} -- cgit v1.2.3 From 500ac1e618410ac453fa4fe83e2348cad8c2418f Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 22 Jun 2024 21:12:39 +0200 Subject: fix --- math/binomial0.cpp | 2 +- math/math.tex | 1 + math/tables/composite.tex | 42 +++++++++++++++++++++--------------------- tcr.pdf | Bin 665092 -> 664604 bytes 4 files changed, 23 insertions(+), 22 deletions(-) (limited to 'math/math.tex') diff --git a/math/binomial0.cpp b/math/binomial0.cpp index d9af917..896a0f1 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 (fac[n] * fac[n-k] % mod) * fac[k] % mod; + return (inv[n] * inv[n-k] % mod) * fac[k] % mod; } diff --git a/math/math.tex b/math/math.tex index 8a30b86..f9a5ea5 100644 --- a/math/math.tex +++ b/math/math.tex @@ -409,6 +409,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/tables/composite.tex b/math/tables/composite.tex index b4c8294..1d06a62 100644 --- a/math/tables/composite.tex +++ b/math/tables/composite.tex @@ -1,26 +1,26 @@ -\begin{tabularx}{\linewidth}{|r|r|r|CICICICICICICICICICICIC|} +\begin{tabularx}{\linewidth}{|r||r|r||r|r|r||C|} \hline - \multicolumn{15}{|c|}{Highly Composite Numbers} \\ + \multicolumn{7}{|c|}{Important Numbers} \\ \hline - $10^x$ & Zahl & Teiler & 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 & 29 & 31 & 37 \\ + $10^x$ & Highly Composite & \# Divs & $<$ Prime & $>$ Prime & \# Primes & \\ \hline - 1 & 6 & 4 & 1 & 1 & & & & & & & & & & \\ - 2 & 60 & 12 & 2 & 1 & 1 & & & & & & & & & \\ - 3 & 840 & 32 & 3 & 1 & 1 & 1 & & & & & & & &\\ - 4 & 7560 & 64 & 3 & 3 & 1 & 1 & & & & & & & & \\ - 5 & 83160 & 128 & 3 & 3 & 1 & 1 & 1 & & & & & & & \\ - 6 & 720720 & 240 & 4 & 2 & 1 & 1 & 1 & 1 & & & & & & \\ - 7 & 8648640 & 448 & 6 & 3 & 1 & 1 & 1 & 1 & & & & & & \\ - 8 & 73513440 & 768 & 5 & 3 & 1 & 1 & 1 & 1 & 1 & & & & & \\ - 9 & 735134400 & 1344 & 6 & 3 & 2 & 1 & 1 & 1 & 1 & & & & & \\ - 10 & 6983776800 & 2304 & 5 & 3 & 2 & 1 & 1 & 1 & 1 & 1 & & & & \\ - 11 & 97772875200 & 4032 & 6 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & & & & \\ - 12 & 963761198400 & 6720 & 6 & 4 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & & & \\ - 13 & 9316358251200 & 10752 & 6 & 3 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & & \\ - 14 & 97821761637600 & 17280 & 5 & 4 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & & \\ - 15 & 866421317361600 & 26880 & 6 & 4 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \\ - 16 & 8086598962041600 & 41472 & 8 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \\ - 17 & 74801040398884800 & 64512 & 6 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ - 18 & 897612484786617600 & 103680 & 8 & 4 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ + 1 & 6 & 4 & $-3$ & $+1$ & 4 & \\ + 2 & 60 & 12 & $-3$ & $+1$ & 25 & \\ + 3 & 840 & 32 & $-3$ & $+9$ & 168 & \\ + 4 & 7\,560 & 64 & $-27$ & $+7$ & 1\,229 & \\ + 5 & 83\,160 & 128 & $-9$ & $+3$ & 9\,592 & \\ + 6 & 720\,720 & 240 & $-17$ & $+3$ & 78\,498 & \\ + 7 & 8\,648\,640 & 448 & $-9$ & $+19$ & 664\,579 & \\ + 8 & 73\,513\,440 & 768 & $-11$ & $+7$ & 5\,761\,455 & \\ + 9 & 735\,134\,400 & 1\,344 & $-63$ & $+7$ & 50\,847\,534 & \\ + 10 & 6\,983\,776\,800 & 2\,304 & $-33$ & $+19$ & 455\,052\,511 & \\ + 11 & 97\,772\,875\,200 & 4\,032 & $-23$ & $+3$ & 4\,118\,054\,813 & \\ + 12 & 963\,761\,198\,400 & 6\,720 & $-11$ & $+39$ & 37\,607\,912\,018 & \\ + 13 & 9\,316\,358\,251\,200 & 10\,752 & $-29$ & $+37$ & 346\,065\,536\,839 & \\ + 14 & 97\,821\,761\,637\,600 & 17\,280 & $-27$ & $+31$ & 3\,204\,941\,750\,802 & \\ + 15 & 866\,421\,317\,361\,600 & 26\,880 & $-11$ & $+37$ & 29\,844\,570\,422\,669 & \\ + 16 & 8\,086\,598\,962\,041\,600 & 41\,472 & $-63$ & $+61$ & 279\,238\,341\,033\,925 & \\ + 17 & 74\,801\,040\,398\,884\,800 & 64\,512 & $-3$ & $+3$ & 2\,623\,557\,157\,654\,233 & \\ + 18 & 897\,612\,484\,786\,617\,600 & 103\,680 & $-11$ & $+3$ & 24\,739\,954\,287\,740\,860 & \\ \hline \end{tabularx} diff --git a/tcr.pdf b/tcr.pdf index c22d0d5..63ebc4a 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3