diff options
Diffstat (limited to 'math/math.tex')
| -rw-r--r-- | math/math.tex | 3 |
1 files changed, 1 insertions, 2 deletions
diff --git a/math/math.tex b/math/math.tex index 31fbdd6..edaebd1 100644 --- a/math/math.tex +++ b/math/math.tex @@ -98,7 +98,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \end{methods} \sourcecode{math/linearRecurence.cpp} Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden: - \small $$\renewcommand\arraystretch{1.5} \setlength\arraycolsep{3pt} \begin{pmatrix} @@ -244,7 +243,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: 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^{cnt[x]}-1$ nicht leere Subsequences in $A$, die nur Vielfache von $x$ enthalten. + 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)$. \sourcecode{math/mobius.cpp} \end{algorithm} |