diff options
Diffstat (limited to 'math')
| -rw-r--r-- | math/binomial.cpp | 4 | ||||
| -rw-r--r-- | math/chineseRemainder.cpp | 18 | ||||
| -rw-r--r-- | math/math.tex | 11 | ||||
| -rw-r--r-- | math/maxTeilfeld.cpp | 15 | ||||
| -rw-r--r-- | math/millerRabin.cpp | 18 | ||||
| -rw-r--r-- | math/primeSieve.cpp | 5 |
6 files changed, 22 insertions, 49 deletions
diff --git a/math/binomial.cpp b/math/binomial.cpp index a8f1561..9605820 100644 --- a/math/binomial.cpp +++ b/math/binomial.cpp @@ -1,8 +1,8 @@ // Laufzeit: O(k) -ll calc_binom(ll n, ll k) { +ll calc_binom(ll n, ll k) { // Sehr sicher gegen Overflows. ll r = 1, d; if (k > n) return 0; - for (d = 1; d <= k; d++) { + for (d = 1; d <= k; d++) { // Reihenfolge garantiert Teilbarkeit. r *= n--; r /= d; } diff --git a/math/chineseRemainder.cpp b/math/chineseRemainder.cpp index 2cf12f7..ac1b71e 100644 --- a/math/chineseRemainder.cpp +++ b/math/chineseRemainder.cpp @@ -1,10 +1,10 @@ // Laufzeit: O(n * log(n)), n := Anzahl der Kongruenzen -// Nur für teilerfremde Moduli. -// Berechnet das kleinste, nicht negative x, das die Kongruenzen simultan löst. -// Alle Lösungen sind kongruent zum kgV der Moduli (Produkt, falls alle teilerfremd sind). +// Nur für teilerfremde Moduli. Berechnet das kleinste, nicht negative x, +// das alle Kongruenzen simultan löst. Alle Lösungen sind kongruent zum +// kgV der Moduli (Produkt, falls alle teilerfremd sind). struct ChineseRemainder { typedef __int128 lll; - vector<lll> lhs, rhs, module, inv; + vector<lll> lhs, rhs, mods, inv; lll M; // Produkt über die Moduli. Kann leicht überlaufen. ll g(vector<lll> &vec) { @@ -20,17 +20,17 @@ struct ChineseRemainder { void addEquation(ll l, ll r, ll m) { lhs.push_back(l); rhs.push_back(r); - module.push_back(m); + mods.push_back(m); } // Löst das System. ll solve() { - M = accumulate(module.begin(), module.end(), lll(1), multiplies<lll>()); + M = accumulate(mods.begin(), mods.end(), lll(1), multiplies<lll>()); inv.resize(lhs.size()); for (int i = 0; i < (int)lhs.size(); i++) { - lll x = (M / module[i]) % module[i]; - inv[i] = (multInvers(x, module[i]) * (M / module[i])); + lll x = (M / mods[i]) % mods[i]; + inv[i] = (multInv(x, mods[i]) * (M / mods[i])); } - return (multInvers(g(lhs), M) * g(rhs)) % M; + return (multInv(g(lhs), M) * g(rhs)) % M; } }; diff --git a/math/math.tex b/math/math.tex index ca81f4b..f40e551 100644 --- a/math/math.tex +++ b/math/math.tex @@ -51,18 +51,9 @@ Sei $0 \leq x < n$. Definiere $d := \gcd(x, n)$.\newline Vorberechnen, wenn häufig benötigt. \lstinputlisting{math/binomial.cpp} -\subsection{Maximales Teilfeld} -\lstinputlisting{math/maxTeilfeld.cpp} -Obiger Code findet kein maximales Teilfeld, das über das Ende hinausgeht. Dazu: -\begin{enumerate} - \item Finde maximales Teilfeld, das nicht übers Ende geht. - \item Berechne minimales Teilfeld, das nicht über den Rand geht (analog). - \item Nimm Maximum aus gefundenem Maximalen und Allem ohne dem Minimalen. -\end{enumerate} - \subsection{Polynome \& FFT} Multipliziert Polynome $A$ und $B$. -\begin{itemize} +\begin{itemize}[nosep] \item $\deg(A * B) = \deg(A) + \deg(B)$ \item Vektoren \lstinline{a} und \lstinline{b} müssen mindestens Größe $\deg(A * B) + 1$ haben. diff --git a/math/maxTeilfeld.cpp b/math/maxTeilfeld.cpp deleted file mode 100644 index bbafa3f..0000000 --- a/math/maxTeilfeld.cpp +++ /dev/null @@ -1,15 +0,0 @@ -// N := Länge des Feldes. -// Laufzeit: O(N) -int maxStart = 1, maxLen = 0, curStart = 1, len = 0; -double maxValue = 0, sum = 0; -for (int pos = 0; pos < N; pos++) { - sum += values[pos]; - len++; - if (sum > maxValue) { // Neues Maximum. - maxValue = sum; maxStart = curStart; maxLen = len; - } - if (sum < 0) { // Alles zurücksetzen. - curStart = pos +2; len = 0; sum = 0; - } -} -// maxSum := maximaler Wert, maxStart := Startposition, maxLen := Länge der Sequenz diff --git a/math/millerRabin.cpp b/math/millerRabin.cpp index d41f33a..fd856d1 100644 --- a/math/millerRabin.cpp +++ b/math/millerRabin.cpp @@ -1,19 +1,17 @@ -// Theoretisch: n < 318,665,857,834,031,151,167,461 (> 10^23) -// Praktisch: n <= 10^18 (long long) -// Laufzeit: O(log n) +// Laufzeit: O(log n). Exakt, nicht propabilistisch. bool isPrime(ll n) { if(n == 2) return true; if(n < 2 || n % 2 == 0) return false; - ll d=n-1,j=0; + ll d = n - 1, j = 0; while(d % 2 == 0) d >>= 1, j++; - for(int a = 2; a <= min((ll)37, n-1); a++) { - ll v = pow_mod(a, d, n); - if(v == 1 || v == n-1) continue; + for(int a = 2; a <= min((ll)37, n - 1); a++) { + ll v = powMod(a, d, n); // Implementierung von oben. + if(v == 1 || v == n - 1) continue; for(int i = 1; i <= j; i++) { - v = mult_mod(v, v, n); - if(v == n-1 || v <= 1) break; + v = multMod(v, v, n); // Implementierung von oben. + if(v == n - 1 || v <= 1) break; } - if(v != n-1) return false; + if(v != n - 1) return false; } return true; } diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp index 5e8d6f8..37ea12c 100644 --- a/math/primeSieve.cpp +++ b/math/primeSieve.cpp @@ -9,13 +9,12 @@ inline bool check(int x) { // Diese Methode zum Lookup verwenden. else return !isPrime[x / 2]; } -inline int primeSieve(int n) { // Gibt die Anzahl der Primzahlen <= n zurück. +inline int primeSieve(int n) { // Rückgabe: Anzahl der Primzahlen <= n. int counter = 1; for (int i = 3; i <= min(N, n); i += 2) { if (!isPrime[i / 2]) { for (int j = 3 * i; j <= min(N, n); j+= 2 * i) isPrime[j / 2] = 1; counter++; - } - } + }} return counter; } |