diff options
Diffstat (limited to 'math')
| -rw-r--r-- | math/longestIncreasingSubsequence.cpp | 2 | ||||
| -rw-r--r-- | math/math.tex | 16 | ||||
| -rw-r--r-- | math/millerRabin.cpp | 2 | ||||
| -rw-r--r-- | math/polynomial.cpp | 2 | ||||
| -rw-r--r-- | math/primitiveRoot.cpp | 6 | ||||
| -rw-r--r-- | math/tables/series.tex | 2 | ||||
| -rw-r--r-- | math/transforms/fftMul.cpp | 2 |
7 files changed, 16 insertions, 16 deletions
diff --git a/math/longestIncreasingSubsequence.cpp b/math/longestIncreasingSubsequence.cpp index c2c5f3e..99bb141 100644 --- a/math/longestIncreasingSubsequence.cpp +++ b/math/longestIncreasingSubsequence.cpp @@ -2,7 +2,7 @@ vector<int> lis(vector<int> &seq) { int n = sz(seq), lisLength = 0, lisEnd = 0; vector<int> L(n), L_id(n), parents(n); for (int i = 0; i < n; i++) { - int pos = upper_bound(L.begin(), L.begin() + lisLength, + int pos = upper_bound(L.begin(), L.begin() + lisLength, seq[i]) - L.begin(); L[pos] = seq[i]; L_id[pos] = i; diff --git a/math/math.tex b/math/math.tex index e640814..235c508 100644 --- a/math/math.tex +++ b/math/math.tex @@ -38,7 +38,7 @@ %\end{multicols} %\vspace{-2.75em} \begin{itemize} - \item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten! + \item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten! \end{itemize} \begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus} @@ -165,8 +165,8 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/linearSieve.cpp} \textbf{\textsc{Möbius} Funtkion:} \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)=+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} @@ -293,7 +293,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden: $$\renewcommand\arraystretch{1.5} \setlength\arraycolsep{3pt} - \begin{pmatrix} + \begin{pmatrix} c_{n-1} & c_{n-2} & \smash{\cdots} & \smash{\cdots} & c_0 \\ 1 & 0 & \smash{\cdots} & \smash{\cdots} & 0 \\ 0 & \smash{\ddots} & \smash{\ddots} & & \smash{\vdots} \\ @@ -301,7 +301,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: 0 & \smash{\cdots} & 0 & 1 & 0 \\ \end{pmatrix}^k \times~~ - \begin{pmatrix} + \begin{pmatrix} f(n-1) \\ f(n-2) \\ \smash{\vdots} \\ @@ -309,7 +309,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: f(0) \\ \end{pmatrix} ~~=~~ - \begin{pmatrix} + \begin{pmatrix} f(n-1+k) \\ f(n-2+k) \\ \smash{\vdots} \\ @@ -364,7 +364,7 @@ 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\} +\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)$. @@ -372,7 +372,7 @@ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \text \subsection{Kombinatorik} \paragraph{Wilsons Theorem} -A number $n$ is prime if and only if +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*} diff --git a/math/millerRabin.cpp b/math/millerRabin.cpp index e4d2f6e..c6a782f 100644 --- a/math/millerRabin.cpp +++ b/math/millerRabin.cpp @@ -1,5 +1,5 @@ constexpr ll bases32[] = {2, 7, 61}; -constexpr ll bases64[] = {2, 325, 9375, 28178, 450775, +constexpr ll bases64[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; bool isPrime(ll n) { if (n < 2 || n % 2 == 0) return n == 2; diff --git a/math/polynomial.cpp b/math/polynomial.cpp index f7d9a89..44f6207 100644 --- a/math/polynomial.cpp +++ b/math/polynomial.cpp @@ -62,4 +62,4 @@ struct poly { s.trim(); r.trim(); return {s, r}; } -}; +}; diff --git a/math/primitiveRoot.cpp b/math/primitiveRoot.cpp index 7973c24..464bdb3 100644 --- a/math/primitiveRoot.cpp +++ b/math/primitiveRoot.cpp @@ -1,12 +1,12 @@ bool isPrimitive(ll g, ll n, ll phi, map<ll, int> phiFacs) { if (g == 1) return n == 2; - for (auto& f : phiFacs) - if (1 == powMod(g, phi / f.first, n)) return false; + for (auto [f, _] : phiFacs) + if (powMod(g, phi / f, n) == 1) return false; return true; } bool isPrimitive(ll g, ll n) { - ll phin = phi(n); //isPrime(n) => phi(n) = n - 1 + ll phin = phi(n); //isPrime(n) => phi(n) = n - 1 map<ll, int> phiFacs; factor(phin, phiFacs); return isPrimitive(g, n, phin, phiFacs); diff --git a/math/tables/series.tex b/math/tables/series.tex index f7e7839..3042781 100644 --- a/math/tables/series.tex +++ b/math/tables/series.tex @@ -3,7 +3,7 @@ \multicolumn{4}{|c|}{Reihen} \\ \hline $\sum\limits_{i = 1}^n i = \frac{n(n+1)}{2}$ & - $\sum\limits_{i = 1}^n i^2 = \frac{n(n + 1)(2n + 1)}{6}$ & + $\sum\limits_{i = 1}^n i^2 = \frac{n(n + 1)(2n + 1)}{6}$ & $\sum\limits_{i = 1}^n i^3 = \frac{n^2 (n + 1)^2}{4}$ & $H_n = \sum\limits_{i = 1}^n \frac{1}{i}$ \\ \grayhline diff --git a/math/transforms/fftMul.cpp b/math/transforms/fftMul.cpp index c8de19a..a1205f6 100644 --- a/math/transforms/fftMul.cpp +++ b/math/transforms/fftMul.cpp @@ -11,4 +11,4 @@ vector<cplx> mul(vector<cplx>& a, vector<cplx>& b) { d[i] = x * y; } return fft(d, true); -} +} |