diff options
Diffstat (limited to 'content/math')
43 files changed, 820 insertions, 811 deletions
diff --git a/content/math/berlekampMassey.cpp b/content/math/berlekampMassey.cpp index 29e084f..85a1031 100644 --- a/content/math/berlekampMassey.cpp +++ b/content/math/berlekampMassey.cpp @@ -1,6 +1,6 @@ constexpr ll mod = 1'000'000'007; vector<ll> BerlekampMassey(const vector<ll>& s) { - int n = sz(s), L = 0, m = 0; + int n = ssize(s), L = 0, m = 0; vector<ll> C(n), B(n), T; C[0] = B[0] = 1; diff --git a/content/math/bigint.cpp b/content/math/bigint.cpp index 1b3b953..a40f515 100644 --- a/content/math/bigint.cpp +++ b/content/math/bigint.cpp @@ -7,9 +7,9 @@ struct bigint { bigint() : sign(1) {} - bigint(ll v) {*this = v;} + bigint(ll v) { *this = v; } - bigint(const string &s) {read(s);} + bigint(const string &s) { read(s); } void operator=(ll v) { sign = 1; @@ -22,10 +22,11 @@ struct bigint { bigint operator+(const bigint& v) const { if (sign == v.sign) { bigint res = v; - for (ll i = 0, carry = 0; i < max(sz(a), sz(v.a)) || carry; ++i) { - if (i == sz(res.a)) + for (ll i = 0, carry = 0; + i < max(ssize(a), ssize(v.a)) || carry; ++i) { + if (i == ssize(res.a)) res.a.push_back(0); - res.a[i] += carry + (i < sz(a) ? a[i] : 0); + res.a[i] += carry + (i < ssize(a) ? a[i] : 0); carry = res.a[i] >= base; if (carry) res.a[i] -= base; @@ -39,8 +40,8 @@ struct bigint { if (sign == v.sign) { if (abs() >= v.abs()) { bigint res = *this; - for (ll i = 0, carry = 0; i < sz(v.a) || carry; ++i) { - res.a[i] -= carry + (i < sz(v.a) ? v.a[i] : 0); + for (ll i = 0, carry = 0; i < ssize(v.a) || carry; ++i) { + res.a[i] -= carry + (i < ssize(v.a) ? v.a[i] : 0); carry = res.a[i] < 0; if (carry) res.a[i] += base; } @@ -54,8 +55,8 @@ struct bigint { void operator*=(ll v) { if (v < 0) sign = -sign, v = -v; - for (ll i = 0, carry = 0; i < sz(a) || carry; ++i) { - if (i == sz(a)) a.push_back(0); + for (ll i = 0, carry = 0; i < ssize(a) || carry; ++i) { + if (i == ssize(a)) a.push_back(0); ll cur = a[i] * v + carry; carry = cur / base; a[i] = cur % base; @@ -74,12 +75,12 @@ struct bigint { bigint a = a1.abs() * norm; bigint b = b1.abs() * norm; bigint q, r; - q.a.resize(sz(a.a)); - for (ll i = sz(a.a) - 1; i >= 0; i--) { + q.a.resize(ssize(a.a)); + for (ll i = ssize(a.a) - 1; i >= 0; i--) { r *= base; r += a.a[i]; - ll s1 = sz(r.a) <= sz(b.a) ? 0 : r.a[sz(b.a)]; - ll s2 = sz(r.a) <= sz(b.a) - 1 ? 0 : r.a[sz(b.a) - 1]; + ll s1 = ssize(r.a) <= ssize(b.a) ? 0 : r.a[ssize(b.a)]; + ll s2 = ssize(r.a) <= ssize(b.a) - 1 ? 0 : r.a[ssize(b.a) - 1]; ll d = (base * s1 + s2) / b.a.back(); r -= b * d; while (r < 0) r += b, --d; @@ -102,7 +103,7 @@ struct bigint { void operator/=(ll v) { if (v < 0) sign = -sign, v = -v; - for (ll i = sz(a) - 1, rem = 0; i >= 0; --i) { + for (ll i = ssize(a) - 1, rem = 0; i >= 0; --i) { ll cur = a[i] + rem * base; a[i] = cur / v; rem = cur % v; @@ -119,7 +120,7 @@ struct bigint { ll operator%(ll v) const { if (v < 0) v = -v; ll m = 0; - for (ll i = sz(a) - 1; i >= 0; --i) + for (ll i = ssize(a) - 1; i >= 0; --i) m = (a[i] + m * base) % v; return m * sign; } @@ -139,9 +140,9 @@ struct bigint { bool operator<(const bigint& v) const { if (sign != v.sign) return sign < v.sign; - if (sz(a) != sz(v.a)) - return sz(a) * sign < sz(v.a) * v.sign; - for (ll i = sz(a) - 1; i >= 0; i--) + if (ssize(a) != ssize(v.a)) + return ssize(a) * sign < ssize(v.a) * v.sign; + for (ll i = ssize(a) - 1; i >= 0; i--) if (a[i] != v.a[i]) return a[i] * sign < v.a[i] * sign; return false; @@ -169,7 +170,7 @@ struct bigint { } bool isZero() const { - return a.empty() || (sz(a) == 1 && a[0] == 0); + return a.empty() || (ssize(a) == 1 && a[0] == 0); } bigint operator-() const { @@ -186,7 +187,7 @@ struct bigint { ll longValue() const { ll res = 0; - for (ll i = sz(a) - 1; i >= 0; i--) + for (ll i = ssize(a) - 1; i >= 0; i--) res = res * base + a[i]; return res * sign; } @@ -195,11 +196,11 @@ struct bigint { sign = 1; a.clear(); ll pos = 0; - while (pos < sz(s) && (s[pos] == '-' || s[pos] == '+')) { + while (pos < ssize(s) && (s[pos] == '-' || s[pos] == '+')) { if (s[pos] == '-') sign = -sign; ++pos; } - for (ll i = sz(s) - 1; i >= pos; i -= base_digits) { + for (ll i = ssize(s) - 1; i >= pos; i -= base_digits) { ll x = 0; for (ll j = max(pos, i - base_digits + 1); j <= i; j++) x = x * 10 + s[j] - '0'; @@ -218,13 +219,13 @@ struct bigint { friend ostream& operator<<(ostream& stream, const bigint& v) { if (v.sign == -1) stream << '-'; stream << (v.a.empty() ? 0 : v.a.back()); - for (ll i = sz(v.a) - 2; i >= 0; --i) + for (ll i = ssize(v.a) - 2; i >= 0; --i) stream << setw(base_digits) << setfill('0') << v.a[i]; return stream; } static vll karatsubaMultiply(const vll& a, const vll& b) { - ll n = sz(a); + ll n = ssize(a); vll res(n + n); if (n <= 32) { for (ll i = 0; i < n; i++) @@ -242,25 +243,25 @@ struct bigint { for (ll i = 0; i < k; i++) a2[i] += a1[i]; for (ll i = 0; i < k; i++) b2[i] += b1[i]; vll r = karatsubaMultiply(a2, b2); - for (ll i = 0; i < sz(a1b1); i++) r[i] -= a1b1[i]; - for (ll i = 0; i < sz(a2b2); i++) r[i] -= a2b2[i]; - for (ll i = 0; i < sz(r); i++) res[i + k] += r[i]; - for (ll i = 0; i < sz(a1b1); i++) res[i] += a1b1[i]; - for (ll i = 0; i < sz(a2b2); i++) res[i + n] += a2b2[i]; + for (ll i = 0; i < ssize(a1b1); i++) r[i] -= a1b1[i]; + for (ll i = 0; i < ssize(a2b2); i++) r[i] -= a2b2[i]; + for (ll i = 0; i < ssize(r); i++) res[i + k] += r[i]; + for (ll i = 0; i < ssize(a1b1); i++) res[i] += a1b1[i]; + for (ll i = 0; i < ssize(a2b2); i++) res[i + n] += a2b2[i]; return res; } bigint operator*(const bigint& v) const { vll ta(a.begin(), a.end()); vll va(v.a.begin(), v.a.end()); - while (sz(ta) < sz(va)) ta.push_back(0); - while (sz(va) < sz(ta)) va.push_back(0); - while (sz(ta) & (sz(ta) - 1)) + while (ssize(ta) < ssize(va)) ta.push_back(0); + while (ssize(va) < ssize(ta)) va.push_back(0); + while (ssize(ta) & (ssize(ta) - 1)) ta.push_back(0), va.push_back(0); vll ra = karatsubaMultiply(ta, va); bigint res; res.sign = sign * v.sign; - for (ll i = 0, carry = 0; i < sz(ra); i++) { + for (ll i = 0, carry = 0; i < ssize(ra); i++) { ll cur = ra[i] + carry; res.a.push_back(cur % base); carry = cur / base; diff --git a/content/math/binomial0.cpp b/content/math/binomial0.cpp index 5f2ccaa..8b436a2 100644 --- a/content/math/binomial0.cpp +++ b/content/math/binomial0.cpp @@ -8,7 +8,7 @@ void precalc() { for (int i = lim - 1; i > 0; i--) inv[i-1] = inv[i] * i % mod; } -ll calc_binom(ll n, ll k) { +ll 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/binomial1.cpp b/content/math/binomial1.cpp index dab20b3..34f13ed 100644 --- a/content/math/binomial1.cpp +++ b/content/math/binomial1.cpp @@ -1,7 +1,7 @@ -ll calc_binom(ll n, ll k) { +ll binom(ll n, ll k) { if (k > n) return 0; ll r = 1; - for (ll d = 1; d <= k; d++) {// Reihenfolge => Teilbarkeit + for (ll d = 1; d <= k; d++) { // Reihenfolge => Teilbarkeit r *= n--, r /= d; } return r; diff --git a/content/math/binomial2.cpp b/content/math/binomial2.cpp index 4531505..bb6a035 100644 --- a/content/math/binomial2.cpp +++ b/content/math/binomial2.cpp @@ -20,7 +20,7 @@ ll binomPPow(ll n, ll k, ll p) { return res; } -ll calc_binom(ll n, ll k) { +ll binom(ll n, ll k) { if (k > n) return 0; ll res = 1; k = min(k, n - k); diff --git a/content/math/binomial3.cpp b/content/math/binomial3.cpp index 7a6ab4e..8a51dac 100644 --- a/content/math/binomial3.cpp +++ b/content/math/binomial3.cpp @@ -1,4 +1,4 @@ -ll calc_binom(ll n, ll k, ll p) { +ll binom(ll n, ll k, ll p) { assert(n < p); //wichtig: sonst falsch! if (k > n) return 0; ll x = k % 2 != 0 ? p-1 : 1; diff --git a/content/math/discreteLogarithm.cpp b/content/math/discreteLogarithm.cpp index 68866e0..844bd27 100644 --- a/content/math/discreteLogarithm.cpp +++ b/content/math/discreteLogarithm.cpp @@ -5,11 +5,11 @@ ll dlog(ll a, ll b, ll m) { //a > 0! vals[i] = {e, i}; } vals.emplace_back(m, 0); - sort(all(vals)); + ranges::sort(vals); ll fact = powMod(a, m - bound - 1, m); for (ll i = 0; i < m; i += bound, b = (b * fact) % m) { - auto it = lower_bound(all(vals), pair<ll, ll>{b, 0}); + auto it = ranges::lower_bound(vals, pair<ll, ll>{b, 0}); if (it->first == b) { return (i + it->second) % m; }} diff --git a/content/math/divisors.cpp b/content/math/divisors.cpp index 5afd4fb..2a17f54 100644 --- a/content/math/divisors.cpp +++ b/content/math/divisors.cpp @@ -2,7 +2,7 @@ ll countDivisors(ll n) { ll res = 1; for (ll i = 2; i * i * i <= n; i++) { ll c = 0; - while (n % i == 0) {n /= i; c++;} + while (n % i == 0) { n /= i; c++; } res *= c + 1; } if (isPrime(n)) res *= 2; diff --git a/content/math/gauss.cpp b/content/math/gauss.cpp index d431e52..719f573 100644 --- a/content/math/gauss.cpp +++ b/content/math/gauss.cpp @@ -7,7 +7,7 @@ void takeAll(int n, int line) { for (int i = 0; i < n; i++) { if (i == line) continue; double diff = mat[i][line]; - for (int j = 0; j < sz(mat[i]); j++) { + for (int j = 0; j < ssize(mat[i]); j++) { mat[i][j] -= diff * mat[line][j]; }}} @@ -22,7 +22,7 @@ int gauss(int n) { if (abs(mat[i][i]) > EPS) { normalLine(i); takeAll(n, i); - done[i] = true; + done[i] = true; }} for (int i = 0; i < n; i++) { // gauss fertig, prüfe Lösung bool allZero = true; diff --git a/content/math/inversions.cpp b/content/math/inversions.cpp index 9e47f9b..289161f 100644 --- a/content/math/inversions.cpp +++ b/content/math/inversions.cpp @@ -1,7 +1,7 @@ ll inversions(const vector<ll>& v) { Tree<pair<ll, ll>> t; //ordered statistics tree @\sourceref{datastructures/pbds.cpp}@ ll res = 0; - for (ll i = 0; i < sz(v); i++) { + for (ll i = 0; i < ssize(v); i++) { res += i - t.order_of_key({v[i], i}); t.insert({v[i], i}); } diff --git a/content/math/inversionsMerge.cpp b/content/math/inversionsMerge.cpp index 8235b11..50fe37b 100644 --- a/content/math/inversionsMerge.cpp +++ b/content/math/inversionsMerge.cpp @@ -2,26 +2,26 @@ ll merge(vector<ll>& v, vector<ll>& left, vector<ll>& right) { int a = 0, b = 0, i = 0; ll inv = 0; - while (a < sz(left) && b < sz(right)) { + while (a < ssize(left) && b < ssize(right)) { if (left[a] < right[b]) v[i++] = left[a++]; else { - inv += sz(left) - a; + inv += ssize(left) - a; v[i++] = right[b++]; } } - while (a < sz(left)) v[i++] = left[a++]; - while (b < sz(right)) v[i++] = right[b++]; + while (a < ssize(left)) v[i++] = left[a++]; + while (b < ssize(right)) v[i++] = right[b++]; return inv; } ll mergeSort(vector<ll> &v) { // Sortiert v und gibt Inversionszahl zurück. - int n = sz(v); + int n = ssize(v); vector<ll> left(n / 2), right((n + 1) / 2); for (int i = 0; i < n / 2; i++) left[i] = v[i]; for (int i = n / 2; i < n; i++) right[i - n / 2] = v[i]; ll result = 0; - if (sz(left) > 1) result += mergeSort(left); - if (sz(right) > 1) result += mergeSort(right); + if (ssize(left) > 1) result += mergeSort(left); + if (ssize(right) > 1) result += mergeSort(right); return result + merge(v, left, right); } diff --git a/content/math/lgsFp.cpp b/content/math/lgsFp.cpp index 4c12477..5028782 100644 --- a/content/math/lgsFp.cpp +++ b/content/math/lgsFp.cpp @@ -1,6 +1,7 @@ -vector<int> pivots; // ith pivot is in ith row -void gauss(int n, int m) { - for (int r = 0, c = 0; c < m; c++) { +vector<int> gauss(vector<vector<ll>> &mat) { + int n = ssize(mat), m = ssize(mat[0]); + vector<int> pivots; // ith pivot is in ith row + for (int r = 0, c = 0; r < n && c < m; c++) { for (int i = r; i < n; i++) { if (mat[i][c] != 0){ swap(mat[r], mat[i]); @@ -16,5 +17,7 @@ void gauss(int n, int m) { mat[i][j] = (mat[i][j] - f*mat[r][j] % mod + mod) % mod; }} pivots.push_back(c); - if (++r == n) break; -}} // no solution if pivots.back() == m-1 + r++; + } + return pivots; // no solution if pivots.back() == m-1 +} diff --git a/content/math/linearRecurrence.cpp b/content/math/linearRecurrence.cpp index a8adacd..eb04566 100644 --- a/content/math/linearRecurrence.cpp +++ b/content/math/linearRecurrence.cpp @@ -1,9 +1,9 @@ constexpr ll mod = 998244353; // oder ntt mul @\sourceref{math/transforms/ntt.cpp}@ vector<ll> mul(const vector<ll>& a, const vector<ll>& b) { - vector<ll> c(sz(a) + sz(b) - 1); - for (int i = 0; i < sz(a); i++) { - for (int j = 0; j < sz(b); j++) { + vector<ll> c(ssize(a) + ssize(b) - 1); + for (int i = 0; i < ssize(a); i++) { + for (int j = 0; j < ssize(b); j++) { c[i+j] += a[i]*b[j] % mod; }} for (ll& x : c) x %= mod; @@ -11,7 +11,7 @@ vector<ll> mul(const vector<ll>& a, const vector<ll>& b) { } ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k) { - int n = sz(c); + int n = ssize(c); vector<ll> q(n + 1, 1); for (int i = 0; i < n; i++) q[i + 1] = (mod - c[i]) % mod; vector<ll> p = mul(f, q); diff --git a/content/math/linearRecurrenceOld.cpp b/content/math/linearRecurrenceOld.cpp index 2501e64..f67398d 100644 --- a/content/math/linearRecurrenceOld.cpp +++ b/content/math/linearRecurrenceOld.cpp @@ -1,7 +1,7 @@ constexpr ll mod = 1'000'000'007; vector<ll> modMul(const vector<ll>& a, const vector<ll>& b, const vector<ll>& c) { - ll n = sz(c); + ll n = ssize(c); vector<ll> res(n * 2 + 1); for (int i = 0; i <= n; i++) { //a*b for (int j = 0; j <= n; j++) { @@ -18,8 +18,8 @@ vector<ll> modMul(const vector<ll>& a, const vector<ll>& b, } ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k) { - assert(sz(f) == sz(c)); - vector<ll> tmp(sz(c) + 1), a(sz(c) + 1); + assert(ssize(f) == ssize(c)); + vector<ll> tmp(ssize(c) + 1), a(ssize(c) + 1); tmp[0] = a[1] = 1; //tmp = (x^k) % c for (k++; k > 0; k /= 2) { @@ -28,6 +28,6 @@ ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k) { } ll res = 0; - for (int i = 0; i < sz(c); i++) res += (tmp[i+1] * f[i]) % mod; + for (int i = 0; i < ssize(c); i++) res += (tmp[i+1] * f[i]) % mod; return res % mod; } diff --git a/content/math/linearSieve.cpp b/content/math/linearSieve.cpp index 64440dd..2ea1e94 100644 --- a/content/math/linearSieve.cpp +++ b/content/math/linearSieve.cpp @@ -3,12 +3,12 @@ ll small[N], power[N], sieved[N]; vector<ll> primes; //wird aufgerufen mit (p^k, p, k) für prime p und k > 0 -ll mu(ll pk, ll p, ll k) {return -(k == 1);} -ll phi(ll pk, ll p, ll k) {return pk - pk / p;} -ll div(ll pk, ll p, ll k) {return k+1;} -ll divSum(ll pk, ll p, ll k) {return (pk*p-1) / (p - 1);} -ll square(ll pk, ll p, ll k) {return k % 2 ? pk / p : pk;} -ll squareFree(ll pk, ll p, ll k) {return p;} +ll mu(ll pk, ll p, ll k) { return -(k == 1); } +ll phi(ll pk, ll p, ll k) { return pk - pk / p; } +ll div(ll pk, ll p, ll k) { return k+1; } +ll divSum(ll pk, ll p, ll k) { return (pk*p-1) / (p - 1); } +ll square(ll pk, ll p, ll k) { return k % 2 ? pk / p : pk; } +ll squareFree(ll pk, ll p, ll k) { return p; } void sieve() { // O(N) small[1] = power[1] = sieved[1] = 1; diff --git a/content/math/longestIncreasingSubsequence.cpp b/content/math/longestIncreasingSubsequence.cpp index fcb63b4..e4863d0 100644 --- a/content/math/longestIncreasingSubsequence.cpp +++ b/content/math/longestIncreasingSubsequence.cpp @@ -1,8 +1,8 @@ vector<int> lis(vector<ll>& a) { - int n = sz(a), len = 0; + int n = ssize(a), len = 0; vector<ll> dp(n, INF), dp_id(n), prev(n); for (int i = 0; i < n; i++) { - int pos = lower_bound(all(dp), a[i]) - dp.begin(); + int pos = ranges::lower_bound(dp, a[i]) - begin(dp); dp[pos] = a[i]; dp_id[pos] = i; prev[i] = pos ? dp_id[pos - 1] : -1; diff --git a/content/math/math.tex b/content/math/math.tex index 162c7cc..97b6a24 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -1,588 +1,595 @@ -\section{Mathe}
-
-\begin{algorithm}{Longest Increasing Subsequence}
- \begin{itemize}
- \item \code{lower\_bound} $\Rightarrow$ streng monoton
- \item \code{upper\_bound} $\Rightarrow$ monoton
- \end{itemize}
- \sourcecode{math/longestIncreasingSubsequence.cpp}
-\end{algorithm}
-\vfill\null\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}
- \method{kthperm}{findet $k$-te Permutation \big($k \in [0, n!$)\big)}{n\*\log(n)}
- \end{methods}
- \sourcecode{math/kthperm.cpp}
- \begin{methods}
- \method{permIndex}{bestimmt Index der Permutation \big($\mathit{res} \in [0, n!$)\big)}{n\*\log(n)}
- \end{methods}
- \sourcecode{math/permIndex.cpp}
-\end{algorithm}
-\clearpage
-
-\subsection{Mod-Exponent und Multiplikation über $\boldsymbol{\mathbb{F}_p}$}
-%\vspace{-1.25em}
-%\begin{multicols}{2}
-\method{mulMod}{berechnet $a \cdot b \bmod n$}{\log(b)}
-\sourcecode{math/modMulIterativ.cpp}
-% \vfill\null\columnbreak
-\method{powMod}{berechnet $a^b \bmod n$}{\log(b)}
-\sourcecode{math/modPowIterativ.cpp}
-%\end{multicols}
-%\vspace{-2.75em}
-\begin{itemize}
- \item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten!
-\end{itemize}
-
-\begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus}
- \runtime{\log(a) + \log(b)}
- \sourcecode{math/extendedEuclid.cpp}
-\end{algorithm}
-
-\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(x, m) = 1}$:}
-\begin{itemize}
- \item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit
- $\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(x, m) > 1}$:}\quad Es existiert kein $x^{-1}$.
-% \sourcecode{math/multInv.cpp}
-\sourcecode{math/shortModInv.cpp}
-
-\paragraph{Lemma von \textsc{Bézout}}
-Sei $(x, y)$ eine Lösung der diophantischen Gleichung $ax + by = d$.
-Dann lassen sich wie folgt alle Lösungen berechnen:
-\[
-\left(x + k\frac{b}{\ggT(a, b)},~y - k\frac{a}{\ggT(a, b)}\right)
-\]
-
-\paragraph{\textsc{Pell}-Gleichungen}
-Sei $(\overline{x}, \overline{y})$ die Lösung von $x^2 - ny^2 = 1$, die $x>1$ minimiert.
-Sei $(\tilde{x}, \tilde{y})$ die Lösung von $x^2-ny^2 = c$, die $x>1$ minimiert. Dann lassen
-sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
-\begin{align*}
- x_1&\coloneqq \tilde{x}, & y_1&\coloneqq\tilde{y}\\
- x_{k+1}&\coloneqq \overline{x}x_k+n\overline{y}y_k, & y_{k+1}&\coloneqq\overline{x}y_k+\overline{y}x_k
-\end{align*}
-
-\begin{algorithm}{Lineare Kongruenz}
- \begin{itemize}
- \item Kleinste Lösung $x$ für $ax\equiv b\pmod{m}$.
- \item Weitere Lösungen unterscheiden sich um \raisebox{2pt}{$\frac{m}{g}$}, es gibt
- also $g$ Lösungen modulo $m$.
- \end{itemize}
- \sourcecode{math/linearCongruence.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Chinesischer Restsatz}
- \begin{itemize}
- \item Extrem anfällig gegen Overflows. Evtl. häufig 128-Bit Integer verwenden.
- \item Direkte Formel für zwei Kongruenzen $x \equiv a \bmod n$, $x \equiv b \bmod m$:
- \[
- x \equiv a - y \cdot n \cdot \frac{a - b}{d} \bmod \frac{mn}{d}
- \qquad \text{mit} \qquad
- d := \ggT(n, m) = yn + zm
- \]
- Formel kann auch für nicht teilerfremde Moduli verwendet werden.
- Sind die Moduli nicht teilerfremd, existiert genau dann eine Lösung,
- 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{algorithm}
-
-\begin{algorithm}{Primzahltest \& Faktorisierung}
- \method{isPrime}{prüft ob Zahl prim ist}{\log(n)^2}
- \sourcecode{math/millerRabin.cpp}
- \method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}4]{n}}
- \sourcecode{math/rho.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Teiler}
- \begin{methods}
- \method{countDivisors}{Zählt Teiler von $n$}{\sqrt[\leftroot{3}\uproot{2}3]{n}}
- \end{methods}
- \sourcecode{math/divisors.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Matrix-Exponent}
- \begin{methods}
- \method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3}
- \method{calc}{berechnet $m^b\cdot$}{\log(b)\cdot n^2}
- \end{methods}
- \textbf{Tipp:} wenn \code{v[x]=1} und \code{0} sonst, dann ist \code{res[y]} = $m^b_{y,x}$.
- \sourcecode{math/matrixPower.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Lineare Rekurrenz}
- \begin{methods}
- \method{BerlekampMassey}{Berechnet eine lineare Rekurrenz $n$-ter Ordnung}{n^2}
- \method{}{aus den ersten $2n$ Werte}{}
- \end{methods}
- \sourcecode{math/berlekampMassey.cpp}
- Sei $f(n)=c_{0}f(n-1)+c_{1}f(n-2)+\dots + c_{n-1}f(0)$ eine lineare Rekurrenz.
-
- \begin{methods}
- \method{kthTerm}{Berechnet $k$-ten Term einer Rekurrenz $n$-ter Ordnung}{\log(k)\cdot \text{mul}(n)}
- \end{methods}
- Die Polynom-Multiplikation kann auch mit NTT gemacht werden!
- \sourcecode{math/linearRecurrence.cpp}
- Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden:
- $$\renewcommand\arraystretch{1.5}
- \setlength\arraycolsep{3pt}
- \begin{pmatrix}
- c_{0} & c_{1} & \smash{\cdots} & \smash{\cdots} & c_{n-1} \\
- 1 & 0 & \smash{\cdots} & \smash{\cdots} & 0 \\
- 0 & \smash{\ddots} & \smash{\ddots} & & \smash{\vdots} \\
- \smash{\vdots} & \smash{\ddots} & \smash{\ddots} & \smash{\ddots} & \smash{\vdots} \\
- 0 & \smash{\cdots} & 0 & 1 & 0 \\
- \end{pmatrix}^k
- \times~~
- \begin{pmatrix}
- f(n-1) \\
- f(n-2) \\
- \smash{\vdots} \\
- \smash{\vdots} \\
- f(0) \\
- \end{pmatrix}
- ~~=~~
- \begin{pmatrix}
- f(n-1+k) \\
- f(n-2+k) \\
- \smash{\vdots} \\
- \smash{\vdots} \\
- f(k) \makebox[0pt][l]{\hspace{15pt}$\vcenter{\hbox{\huge$\leftarrow$}}$}\\
- \end{pmatrix}
- $$
-\end{algorithm}
-
-\begin{algorithm}{Diskreter Logarithmus}
- \begin{methods}
- \method{solve}{bestimmt Lösung $x$ für $a^x=b \bmod m$}{\sqrt{m}\*\log(m)}
- \end{methods}
- \sourcecode{math/discreteLogarithm.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Diskrete Quadratwurzel}
- \begin{methods}
- \method{sqrtMod}{bestimmt Lösung $x$ für $x^2=a \bmod p$ }{\log(p)}
- \end{methods}
- \textbf{Wichtig:} $p$ muss prim sein!
- \sourcecode{math/sqrtModCipolla.cpp}
-\end{algorithm}
-%\columnbreak
-
-\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}{Diskrete \textrm{\textit{n}}-te Wurzel}
- \begin{methods}
- \method{root}{bestimmt Lösung $x$ für $x^a=b \bmod m$ }{\sqrt{m}\*\log(m)}
- \end{methods}
- Alle Lösungen haben die Form $g^{c + \frac{i \cdot \phi(n)}{\gcd(a, \phi(n))}}$
- \sourcecode{math/discreteNthRoot.cpp}
-\end{algorithm}
-
-\begin{algorithm}{\textsc{Legendre}-Symbol}
- Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$:
- \vspace{-0.15cm}\begin{align*}
- \hspace*{3cm}\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*}
- \vspace{-0.05cm}
- \sourcecode{math/legendre.cpp}
-\end{algorithm}
-
-\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.
-
- \begin{methods}
- \method{sieve}{berechnet Primzahlen und co.}{N}
- \method{sieved}{Wert der entsprechenden multiplikativen Funktion}{1}
-
- \method{naive}{Wert der entsprechenden multiplikativen Funktion}{\sqrt{n}}
- \end{methods}
- \textbf{Wichtig:} Sieb rechts ist schneller für \code{isPrime} oder \code{primes}!
-
- \sourcecode{math/linearSieve.cpp}
- \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
- \item $\mu(n)=0$, falls $n$ nicht quadratfrei ist
- \end{itemize}
-
- \textbf{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion:}
- \begin{itemize}
- \item Zählt die relativ primen Zahlen $\leq n$.
- \item $p$ prim, $k \in \mathbb{N}$:
- $~\varphi(p^k) = p^k - p^{k - 1}$
-
- \item \textbf{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}
-\end{algorithm}
-
-\begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}}
- \begin{itemize}
- \item Bis $10^8$ in unter 64MB Speicher (lange Berechnung)
- \end{itemize}
- \begin{methods}
- \method{primeSieve}{berechnet Primzahlen und Anzahl}{N\*\log(\log(N))}
- \method{isPrime}{prüft ob Zahl prim ist}{1}
- \end{methods}
- \sourcecode{math/primeSieve.cpp}
-\end{algorithm}
-
-\begin{algorithm}{\textsc{Möbius}-Inversion}
- \begin{itemize}
- \item Seien $f,g : \mathbb{N} \to \mathbb{N}$ und $g(n) := \sum_{d \vert n}f(d)$.
- Dann ist $f(n) = \sum_{d \vert n}g(d)\mu(\frac{n}{d})$.
- \item $\sum\limits_{d \vert n}\mu(d) =
- \begin{cases*}
- 1 & falls $n = 1$\\
- 0 & sonst
- \end{cases*}$
- \end{itemize}
- \textbf{Beispiel Inklusion/Exklusion:}
- 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^{[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)$.
-\end{algorithm}
-
-\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$}
-\method{gauss}{löst LGS}{n^3}
-\sourcecode{math/lgsFp.cpp}
-
-\subsection{LGS über $\boldsymbol{\mathbb{R}}$}
-\method{gauss}{löst LGS}{n^3}
-\sourcecode{math/gauss.cpp}
-
-\begin{algorithm}{Inversionszahl}
- \vspace{-2pt}
- \sourcecode{math/inversions.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Numerisch Extremstelle bestimmen}
- \sourcecode{math/goldenSectionSearch.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Numerisch Integrieren, Simpsonregel}
- \sourcecode{math/simpson.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}
- Multipliziert Polynome $A$ und $B$.
- \begin{itemize}
- \item $\deg(A \cdot B) = \deg(A) + \deg(B)$
- \item Vektoren \code{a} und \code{b} müssen mindestens Größe
- $\deg(A \cdot B) + 1$ haben.
- Größe muss eine Zweierpotenz sein.
- \item Für ganzzahlige Koeffizienten: \code{(ll)round(real(a[i]))}
- \item \emph{xor}, \emph{or} und \emph{and} Transform funktioniert auch mit \code{double} oder modulo einer Primzahl $p$ falls $p \geq 2^{\texttt{bits}}$
- \end{itemize}
- %\sourcecode{math/fft.cpp}
- %\sourcecode{math/ntt.cpp}
- \sourcecode{math/transforms/fft.cpp}
- \sourcecode{math/transforms/ntt.cpp}
- \sourcecode{math/transforms/bitwiseTransforms.cpp}
- Multiplikation mit 2 transforms statt 3: (nur benutzten wenn nötig!)
- \sourcecode{math/transforms/fftMul.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Operations on Formal Power Series}
- \sourcecode{math/transforms/seriesOperations.cpp}
-\end{algorithm}
-
-\subsection{Kombinatorik}
-
-\paragraph{Wilsons 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\}$)
-\begin{align*}
- (n-1)!\equiv\begin{cases}
- -1\bmod{n},&\mathrm{falls}~n \in \mathbb{P}\\
- \hphantom{-}2\bmod{n},&\mathrm{falls}~n = 4\\
- \hphantom{-}0\bmod{n},&\mathrm{sonst}
- \end{cases}
-\end{align*}
-
-\paragraph{\textsc{Zeckendorfs} 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}
-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}
-\[
- \binom{m}{n} \equiv \prod_{i=0}^k\binom{m_i}{n_i} \bmod{p}.
-\]
-
-%\begin{algorithm}{Binomialkoeffizienten}
-\paragraph{Binomialkoeffizienten}
- Die Anzahl der \mbox{$k$-elementigen} Teilmengen einer \mbox{$n$-elementigen} Menge.
-
- \input{math/tables/binom}
-
- \begin{methods}
- \method{precalc}{berechnet $n!$ und $n!^{-1}$ vor}{\mathit{lim}}
- \method{calc\_binom}{berechnet Binomialkoeffizient}{1}
- \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$
-
- \begin{methods}
- \method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k}
- \end{methods}
- \sourcecode{math/binomial1.cpp}
-
- \begin{methods}
- \method{calc\_binom}{berechnet Binomialkoeffizient modulo Primzahl $p$}{p-n}
- \end{methods}
- \sourcecode{math/binomial3.cpp}
-
-% \begin{methods}
-% \method{calc\_binom}{berechnet Primfaktoren vom Binomialkoeffizient}{n}
-% \end{methods}
-% \textbf{WICHTIG:} braucht alle Primzahlen $\leq n$
-% \sourcecode{math/binomial2.cpp}
-%\end{algorithm}
-
-\paragraph{\textsc{Catalan}-Zahlen:}
-$1,~1,~2,~5,~14,~42,~132,~429,~1430,~4862,~16796,~58786,~208012,~742900$
-\begin{itemize}
- \item Die \textsc{Catalan}-Zahl $C_n$ gibt an:
- \begin{itemize}
- \item Anzahl der Binärbäume mit $n$ nicht unterscheidbaren Knoten.
- \item Anzahl der validen Klammerausdrücke mit $n$ Klammerpaaren.
- \item Anzahl der korrekten Klammerungen von $n+1$ Faktoren.
- \item Anzahl Möglichkeiten ein konvexes Polygon mit $n + 2$ Ecken zu triangulieren.
- \item Anzahl der monotonen Pfade (zwischen gegenüberliegenden Ecken) in
- einem $n \times n$-Gitter, die nicht die Diagonale kreuzen.
- \end{itemize}
-\end{itemize}
-\[C_0 = 1\qquad C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} =
-\frac{1}{n + 1}\binom{2n}{n} = \frac{4n - 2}{n+1} \cdot C_{n-1}\]
-\begin{itemize}
- \item Formel $1$ ohne Division in \runtime{n^2}, Formel $2$ und $3$ in \runtime{n}
-\end{itemize}
-
-\paragraph{\textsc{Catalan}-Convolution}
-\begin{itemize}
- \item Anzahl an Klammerausdrücken mit $n+k$ Klammerpaaren, die mit $\texttt{(}^k$ beginnen.
-\end{itemize}
-\[C^k_0 = 1\qquad C^k_n = \sum\limits_{\mathclap{a_0+a_1+\dots+a_k=n}} C_{a_0}C_{a_1}\cdots C_{a_k} =
-\frac{k+1}{n+k+1}\binom{2n+k}{n} = \frac{(2n+k-1)\cdot(2n+k)}{n(n+k+1)} \cdot C^k_{n-1}\]
-
-\paragraph{\textsc{Euler}-Zahlen 1. Ordnung:}
-$|~1~|~1~|~1,~1~|~1,~4,~1~|~1,~11,~11,~1~|~1,~26,~66,~26,~1~|$
-
-Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Anstiegen.
-Für die $n$-te Zahl gibt es $n$ mögliche Positionen zum Einfügen.
-Dabei wird entweder ein Anstieg in zwei gesplitted oder ein Anstieg um $n$ ergänzt.
-\[\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \quad
-\eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1}=
-\sum_{i=0}^{k} (-1)^i\binom{n+1}{i}(k+1-i)^n\]
-\begin{itemize}
- \item Formel $1$ohne Division in \runtime{n^2}, Formel $2$ erlaubt Berechnung in \runtime{n\log(n)}
-\end{itemize}
-
-\paragraph{\textsc{Euler}-Zahlen 2. Ordnung:}
-$|~1~|~1,~0~|~1,~2,~0~|~1,~8,~6,~0~|~1,~22,~58,~24,~0~|$
-
-Die Anzahl der Permutationen von $\{1,1, \ldots, n,n\}$ mit genau $k$ Anstiegen.
-\[\eulerII{n}{0} = 1 \qquad\eulerII{n}{n} = 0 \qquad\eulerII{n}{k} = (k+1) \eulerII{n-1}{k} + (2n-k-1) \eulerII{n-1}{k-1}\]
-\begin{itemize}
- \item Formel ohne Division in \runtime{n^2}
-\end{itemize}
-
-\paragraph{\textsc{Stirling}-Zahlen 1. Ordnung:}
-$|~1~|~0,~1~|~0,~1,~1~|~0,~2,~3,~1~|~0,~6,~11,~6,~1~|$
-
-Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Zyklen.
-Es gibt zwei Möglichkeiten für die $n$-te Zahl. Entweder sie bildet einen eigene Zyklus, oder sie kann an jeder Position in jedem Zyklus einsortiert werden.
-\[\stirlingI{0}{0} = 1 \qquad
-\stirlingI{n}{0} = \stirlingI{0}{k} = 0 \qquad
-\stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}\]
-\begin{itemize}
- \item Formel ohne Division in \runtime{n^2}
-\end{itemize}
-\[\sum_{k=0}^{n}\pm\stirlingI{n}{k}x^k=x(x-1)(x-2)\cdots(x-n+1)\]
-\begin{itemize}
- \item Berechne Polynom mit FFT und benutzte betrag der Koeffizienten \runtime{n\log(n)^2} (nur ca. gleich große Polynome zusammen multiplizieren beginnend mit $x-k$)
-\end{itemize}
-
-\paragraph{\textsc{Stirling}-Zahlen 2. Ordnung:}
-$|~1~|~0,~1~|~0,~1,~1~|~0,~1,~3,~1~|~0,~1,~7,~6,~1~|$
-
-Die Anzahl der Möglichkeiten $n$ Elemente in $k$ nichtleere Teilmengen zu zerlegen.
-Es gibt $k$ Möglichkeiten die $n$ in eine $n-1$-Partition einzuordnen.
-Dazu kommt der Fall, dass die $n$ in ihrer eigenen Teilmenge (alleine) steht.
-\[\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad
-\stirlingII{n}{0} = 0 \qquad
-\stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1} =
-\frac{1}{k!} \sum\limits_{i=0}^{k} (-1)^{k-i}\binom{k}{i}i^n\]
-\begin{itemize}
- \item Formel $1$ ohne Division in \runtime{n^2}, Formel $2$ in \runtime{n\log(n)}
-\end{itemize}
-
-\paragraph{\textsc{Bell}-Zahlen:}
-$1,~1,~2,~5,~15,~52,~203,~877,~4140,~21147,~115975,~678570,~4213597$
-
-Anzahl der Partitionen von $\{1, \ldots, n\}$.
-Wie \textsc{Stirling}-Zahlen 2. Ordnung ohne Limit durch $k$.
-\vspace{-0.2cm}%
-\[B_0 = 1 \qquad
-B_n = \sum\limits_{k = 0}^{n - 1} B_k\binom{n-1}{k}
-= \sum\limits_{k = 0}^{n}\stirlingII{n}{k}\qquad\qquad B_{p^m+n}\equiv m\cdot B_n + B_{n+1} \bmod{p}\]
-\begin{itemize}
- \item Alternative: $B(n) = \mathrm{EGF}\big(e^{e^n-1}\big)$ (\code{poly_exp} auf Seite \pageref{code:math/transforms/seriesOperations.cpp})
-\end{itemize}
-
-\paragraph{$\boldsymbol{k}$ Partitions:}
-$|~1~|~0,~1~|~0,~1,~1~|~0,~1,~1,~1~|~0,~1,~2,~1,~1~|~0,~1,~2,~2,~1,~1~|~0,~1,~3,~3,~2,~1,~1~|$
-
-Die Anzahl der Partitionen von $n$ in genau $k$ positive Summanden.
-Die Anzahl der Partitionen von $n$ mit größtem Elementen $k$.
-\begin{align*}
- p_0(0)=1 \qquad p_k(n)&=0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0\\[-2pt]
- p_k(n)&= p_k(n-k) + p_{k-1}(n-1)\\[-0.55cm]
-\end{align*}
-\begin{itemize}
- \item Anzahl der Partitionen von $n$ in bis zu $k$ Summanden: $\sum\limits_{i=0}^{k}p_i(n)=p_k(n+k)$
-\end{itemize}
-
-\paragraph{Partitions:}
-$1,~1,~2,~3,~5,~7,~11,~15,~22,~30,~42,~56,~77,~101,~135,~176,~231,~297,~385,~490,~627$
-\[p(n)=\sum_{k=1}^{n} p_k(n)=p_n(2n)=\sum\limits_{k=1}^\infty(-1)^{k+1}\bigg[p\bigg(n - \frac{k(3k-1)}{2}\bigg) + p\bigg(n - \frac{k(3k+1)}{2}\bigg)\bigg]\]
-\begin{itemize}
- \item Rekursion abbrechen wenn argument negativ wird $\Longrightarrow$ Laufzeit $\runtime{\sqrt{n}}$
- \item Alternative: $p(n) = \mathrm{OGF(A)}^{-1}$ mit $A\mkern-1mu\big[\frac{k(3k\pm1)}{2}\big]\coloneqq(-1)^k$ (\code{poly_inv} auf Seite \pageref{code:math/transforms/seriesOperations.cpp})
-\end{itemize}
-
-\subsection{The Twelvefold Way \textnormal{(verteile $n$ Bälle auf $k$ Boxen)}}
-\input{math/tables/twelvefold}
-
-\subsection{Platonische Körper}
-\input{math/tables/platonic}
-
-\input{math/tables/probability}
-
-\subsection{Satz von \textsc{Sprague-Grundy}}
-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\}
-\]
-$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)$.
-
-\subsection{Nim-Spiele}
-\begin{itemize}
- \item[\ding{182}] letzter gewinnt (normal)
- \item[\ding{183}] letzter verliert
-\end{itemize}
-\input{math/tables/nim}
-
-\subsection{Verschiedenes}
-\input{math/tables/stuff}
-
-\begin{algorithm}{Div Sum}
- \method{divSum}{berechnet $\sum_{i=0}^{n-1} \left\lfloor \frac{a\cdot i + b}{m} \right\rfloor$}{\log(n)}
- \textbf{Wichtig:} $b$ darf nicht negativ sein!
- \sourcecode{math/divSum.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Min Mod}
- \begin{methods}
- \method{firstVal}{berechnet den ersten Wert von $0,\ a, \ldots,\ a \cdot i \bmod{m}$,}{\log(m)}
- \method{}{der in $[l, r]$ liegt. Gibt $-1$ zurück, falls er nicht existiert.}{}
- \method{minMod}{berechnet das Minimum von $(a \cdot i + b) \bmod{m}$ für $i \in [0, n)$}{\log(m)}
- \end{methods}
- \textbf{Wichtig:} $0 \leq a, b, l, r < m$
- \sourcecode{math/minMod.cpp}
-\end{algorithm}
-
-\subsection{Reihen}
-\input{math/tables/series}
-
-\subsection{Wichtige Zahlen}
-\input{math/tables/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)}
-\textbf{WICHTIG:} $x$ und $y$ müssen kleiner als $\sqrt{\nicefrac{m}{2}}$ sein!
-\sourcecode{math/recover.cpp}
-
-\optional{
-\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
-\begin{methods}
- \method{init}{berechnet $\pi$ bis $N$}{N\*\log(\log(N))}
- \method{phi}{zählt zu $p_i$ teilerfremde Zahlen $\leq n$ für alle $i \leq k$}{???}
- \method{pi}{zählt Primzahlen $\leq n$ ($n < N^2$)}{n^{2/3}}
-\end{methods}
-\sourcecode{math/piLehmer.cpp}
-
-\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
-\sourcecode{math/piLegendre.cpp}
-}
-
-\begin{algorithm}[optional]{Big Integers}
- \sourcecode{math/bigint.cpp}
-\end{algorithm}
+\section{Mathe} + +\begin{algorithm}{Longest Increasing Subsequence} + \begin{itemize} + \item \code{lower\_bound} $\Rightarrow$ streng monoton + \item \code{upper\_bound} $\Rightarrow$ monoton + \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} + \method{kthperm}{findet $k$-te Permutation \big($k \in [0, n!$)\big)}{n\*\log(n)} + \end{methods} + \sourcecode{math/kthperm.cpp} + \begin{methods} + \method{permIndex}{bestimmt Index der Permutation \big($\mathit{res} \in [0, n!$)\big)}{n\*\log(n)} + \end{methods} + \sourcecode{math/permIndex.cpp} +\end{algorithm} +\columnbreak + +\subsection{Potenzen in $\boldsymbol{\mathbb{Z}/n\mathbb{Z}}$} + \begin{methods} + \method{powMod}{berechnet $a^b \bmod n$}{\log(b)} + \end{methods} + \sourcecode{math/modPowIterativ.cpp} + \begin{itemize} + \item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten! + \end{itemize} + +\optional{ +\subsection{Multiplikation in $\boldsymbol{\mathbb{Z}/n\mathbb{Z}}$ \opthint} + \begin{methods} + \method{mulMod}{berechnet $a \cdot b \bmod n$}{\log(b)} + \end{methods} + \sourcecode{math/modMulIterativ.cpp} +} + +\begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus} + \runtime{\log(a) + \log(b)} + \sourcecode{math/extendedEuclid.cpp} +\end{algorithm} + +\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(x, m) = 1}$:} +\begin{itemize} + \item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit + $\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(x, m) > 1}$:}\quad Es existiert kein $x^{-1}$. +% \sourcecode{math/multInv.cpp} +\sourcecode{math/shortModInv.cpp} + +\paragraph{Lemma von \textsc{Bézout}} +Sei $(x, y)$ eine Lösung der diophantischen Gleichung $ax + by = d$. +Dann lassen sich wie folgt alle Lösungen berechnen: +\[ +\left(x + k\frac{b}{\ggT(a, b)},~y - k\frac{a}{\ggT(a, b)}\right) +\] + +\paragraph{\textsc{Pell}-Gleichungen} +Sei $(\overline{x}, \overline{y})$ die Lösung von $x^2 - ny^2 = 1$, die $x>1$ minimiert. +Sei $(\tilde{x}, \tilde{y})$ die Lösung von $x^2-ny^2 = c$, die $x>1$ minimiert. Dann lassen +sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: +\begin{align*} + x_1&\coloneqq \tilde{x}, & y_1&\coloneqq\tilde{y}\\ + x_{k+1}&\coloneqq \overline{x}x_k+n\overline{y}y_k, & y_{k+1}&\coloneqq\overline{x}y_k+\overline{y}x_k +\end{align*} + +\begin{algorithm}{Lineare Kongruenz} + \begin{itemize} + \item Kleinste Lösung $x$ für $ax\equiv b\pmod{m}$. + \item Weitere Lösungen unterscheiden sich um \raisebox{2pt}{$\frac{m}{g}$}, es gibt + also $g$ Lösungen modulo $m$. + \end{itemize} + \sourcecode{math/linearCongruence.cpp} +\end{algorithm} + +\begin{algorithm}{Chinesischer Restsatz} + \begin{itemize} + \item Extrem anfällig gegen Overflows. Evtl. häufig 128-Bit Integer verwenden. + \item Direkte Formel für zwei Kongruenzen $x \equiv a \bmod n$, $x \equiv b \bmod m$: + \[ + x \equiv a - y \cdot n \cdot \frac{a - b}{d} \bmod \frac{mn}{d} + \qquad \text{mit} \qquad + d := \ggT(n, m) = yn + zm + \] + Formel kann auch für nicht teilerfremde Moduli verwendet werden. + Sind die Moduli nicht teilerfremd, existiert genau dann eine Lösung, + 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{algorithm} + +\begin{algorithm}{Primzahltest \& Faktorisierung} + \method{isPrime}{prüft ob Zahl prim ist}{\log(n)^2} + \sourcecode{math/millerRabin.cpp} + \method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}4]{n}} + \sourcecode{math/rho.cpp} +\end{algorithm} + +\begin{algorithm}{Teiler} + \begin{methods} + \method{countDivisors}{Zählt Teiler von $n$}{\sqrt[\leftroot{3}\uproot{2}3]{n}} + \end{methods} + \sourcecode{math/divisors.cpp} +\end{algorithm} + +\begin{algorithm}{Matrix-Exponent} + \begin{methods} + \method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3} + \method{calc}{berechnet $m^b \cdot v$}{\log(b)\cdot n^2} + \end{methods} + \textbf{Tipp:} wenn \code{v[x]=1} und \code{0} sonst, dann ist \code{res[y]} = $m^b_{y,x}$. + \sourcecode{math/matrixPower.cpp} +\end{algorithm} + +\begin{algorithm}{Lineare Rekurrenz} + \begin{methods} + \method{BerlekampMassey}{Berechnet eine lineare Rekurrenz $n$-ter Ordnung}{n^2} + \method{}{aus den ersten $2n$ Werte}{} + \end{methods} + \sourcecode{math/berlekampMassey.cpp} + Sei $f(n)=c_{0}f(n-1)+c_{1}f(n-2)+\dots + c_{n-1}f(0)$ eine lineare Rekurrenz. + + \begin{methods} + \method{kthTerm}{Berechnet $k$-ten Term einer Rekurrenz $n$-ter Ordnung}{\log(k)\cdot \text{mul}(n)} + \end{methods} + Die Polynom-Multiplikation kann auch mit NTT gemacht werden! + \sourcecode{math/linearRecurrence.cpp} + Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden: + $$\renewcommand\arraystretch{1.5} + \setlength\arraycolsep{3pt} + \begin{pmatrix} + c_{0} & c_{1} & \smash{\cdots} & \smash{\cdots} & c_{n-1} \\ + 1 & 0 & \smash{\cdots} & \smash{\cdots} & 0 \\ + 0 & \smash{\ddots} & \smash{\ddots} & & \smash{\vdots} \\ + \smash{\vdots} & \smash{\ddots} & \smash{\ddots} & \smash{\ddots} & \smash{\vdots} \\ + 0 & \smash{\cdots} & 0 & 1 & 0 \\ + \end{pmatrix}^k + \times~~ + \begin{pmatrix} + f(n-1) \\ + f(n-2) \\ + \smash{\vdots} \\ + \smash{\vdots} \\ + f(0) \\ + \end{pmatrix} + ~~=~~ + \begin{pmatrix} + f(n-1+k) \\ + f(n-2+k) \\ + \smash{\vdots} \\ + \smash{\vdots} \\ + f(k) \makebox[0pt][l]{\hspace{15pt}$\vcenter{\hbox{\huge$\leftarrow$}}$}\\ + \end{pmatrix} + $$ +\end{algorithm} + +\begin{algorithm}{Diskreter Logarithmus} + \begin{methods} + \method{solve}{bestimmt Lösung $x$ für $a^x=b \bmod m$}{\sqrt{m}\*\log(m)} + \end{methods} + \sourcecode{math/discreteLogarithm.cpp} +\end{algorithm} + +\begin{algorithm}{Diskrete Quadratwurzel} + \begin{methods} + \method{sqrtMod}{bestimmt Lösung $x$ für $x^2=a \bmod p$ }{\log(p)} + \end{methods} + \textbf{Wichtig:} $p$ muss prim sein! + \sourcecode{math/sqrtModCipolla.cpp} +\end{algorithm} +%\columnbreak + +\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}{Diskrete \textrm{\textit{n}}-te Wurzel} + \begin{methods} + \method{root}{bestimmt Lösung $x$ für $x^a=b \bmod m$ }{\sqrt{m}\*\log(m)} + \end{methods} + Alle Lösungen haben die Form $g^{c + \frac{i \cdot \phi(n)}{\gcd(a, \phi(n))}}$ + \sourcecode{math/discreteNthRoot.cpp} +\end{algorithm} + +\begin{algorithm}{\textsc{Legendre}-Symbol} + Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$: + \vspace{-0.15cm}\begin{align*} + \hspace*{3cm}\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*} + \vspace{-0.05cm} + \sourcecode{math/legendre.cpp} +\end{algorithm} + +\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. + + \begin{methods} + \method{sieve}{berechnet Primzahlen und co.}{N} + \method{sieved}{Wert der entsprechenden multiplikativen Funktion}{1} + + \method{naive}{Wert der entsprechenden multiplikativen Funktion}{\sqrt{n}} + \end{methods} + \textbf{Wichtig:} Sieb rechts ist schneller für \code{isPrime} oder \code{primes}! + + \sourcecode{math/linearSieve.cpp} + \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 + \item $\mu(n)=0$, falls $n$ nicht quadratfrei ist + \end{itemize} + + \textbf{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion:} + \begin{itemize} + \item Zählt die relativ primen Zahlen $\leq n$. + \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} +\end{algorithm} + +\begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}} + \begin{itemize} + \item Bis $10^8$ in unter 64MB Speicher (lange Berechnung) + \end{itemize} + \begin{methods} + \method{primeSieve}{berechnet Primzahlen und Anzahl}{N\*\log(\log(N))} + \method{isPrime}{prüft ob Zahl prim ist}{1} + \end{methods} + \sourcecode{math/primeSieve.cpp} +\end{algorithm} + +\begin{algorithm}{\textsc{Möbius}-Inversion} + \begin{itemize} + \item Seien $f,g : \mathbb{N} \to \mathbb{N}$ und $g(n) := \sum_{d \vert n}f(d)$. + Dann ist $f(n) = \sum_{d \vert n}g(d)\mu(\frac{n}{d})$. + \item $\sum\limits_{d \vert n}\mu(d) = + \begin{cases*} + 1 & falls $n = 1$\\ + 0 & sonst + \end{cases*}$ + \end{itemize} + \textbf{Beispiel Inklusion/Exklusion:} + 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^{[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)$. +\end{algorithm} + +\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$} +\method{gauss}{löst LGS}{n^3} +\sourcecode{math/lgsFp.cpp} + +\subsection{LGS über $\boldsymbol{\mathbb{R}}$} +\method{gauss}{löst LGS}{n^3} +\sourcecode{math/gauss.cpp} + +\begin{algorithm}{Inversionszahl} + \vspace{-2pt} + \sourcecode{math/inversions.cpp} +\end{algorithm} + +\begin{algorithm}{Numerisch Extremstelle bestimmen} + \sourcecode{math/goldenSectionSearch.cpp} +\end{algorithm} + +\begin{algorithm}{Numerisch Integrieren, Simpsonregel} + \sourcecode{math/simpson.cpp} +\end{algorithm} + +\begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen} + \label{fft} + Multipliziert Polynome $A$ und $B$. + \ifthenelse{\isundefined{\srclink}}{}{% + \hfill + \begin{ocg}[printocg=never]{Source links}{srclinks}{1}% + \href{\srclink{math/transforms/}}{\faExternalLink}% + \end{ocg}% + } + \begin{itemize} + \item $\deg(A \cdot B) = \deg(A) + \deg(B)$ + \item Vektoren \code{a} und \code{b} müssen mindestens Größe + $\deg(A \cdot B) + 1$ haben. + Größe muss eine Zweierpotenz sein. + \item Für ganzzahlige Koeffizienten: \code{(ll)round(real(a[i]))} + \item \emph{or} Transform berechnet sum over subsets + $\rightarrow$ inverse für inclusion/exclusion + \end{itemize} + \sourcecode{math/transforms/fft.cpp} + \sourcecode{math/transforms/ntt.cpp} + \sourcecode{math/transforms/bitwiseTransforms.cpp} + Multiplikation mit 2 Transforms statt 3: (nur benutzen wenn nötig!) + \sourcecode{math/transforms/fftMul.cpp} +\end{algorithm} + +\begin{algorithm}{Operations on Formal Power Series} + \sourcecode{math/transforms/seriesOperations.cpp} +\end{algorithm} + +\subsection{Kombinatorik} + +\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\}$) +\begin{align*} + (n-1)!\equiv\begin{cases} + -1\bmod{n},&\mathrm{falls}~n \in \mathbb{P}\\ + \hphantom{-}2\bmod{n},&\mathrm{falls}~n = 4\\ + \hphantom{-}0\bmod{n},&\mathrm{sonst} + \end{cases} +\end{align*} + +\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}'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} +\[ + \binom{m}{n} \equiv \prod_{i=0}^k\binom{m_i}{n_i} \bmod{p}. +\] + +%\begin{algorithm}{Binomialkoeffizienten} +\paragraph{Binomialkoeffizienten} + Die Anzahl der \mbox{$k$-elementigen} Teilmengen einer \mbox{$n$-elementigen} Menge. + + \input{math/tables/binom} + + \begin{methods} + \method{precalc}{berechnet $n!$ und $n!^{-1}$ vor}{\mathit{lim}} + \method{binom}{berechnet Binomialkoeffizient}{1} + \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$ + + \begin{methods} + \method{binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k} + \end{methods} + \sourcecode{math/binomial1.cpp} + + \optional{ + \begin{methods} + \method{binom}{berechnet Primfaktoren vom Binomialkoeffizient}{n\*\log(n)} + \end{methods} + \opthint \\ + \textbf{WICHTIG:} braucht alle Primzahlen $\leq n$ + \sourcecode{math/binomial2.cpp} + } + + \begin{methods} + \method{binom}{berechnet Binomialkoeffizient modulo Primzahl $p$}{p-n} + \end{methods} + \sourcecode{math/binomial3.cpp} +%\end{algorithm} + +\paragraph{\textsc{Catalan}-Zahlen:} +$1,~1,~2,~5,~14,~42,~132,~429,~1430,~4862,~16796,~58786,~208012,~742900$ +\begin{itemize} + \item Die \textsc{Catalan}-Zahl $C_n$ gibt an: + \begin{itemize} + \item Anzahl der Binärbäume mit $n$ nicht unterscheidbaren Knoten. + \item Anzahl der validen Klammerausdrücke mit $n$ Klammerpaaren. + \item Anzahl der korrekten Klammerungen von $n+1$ Faktoren. + \item Anzahl Möglichkeiten ein konvexes Polygon mit $n + 2$ Ecken zu triangulieren. + \item Anzahl der monotonen Pfade (zwischen gegenüberliegenden Ecken) in + einem $n \times n$-Gitter, die nicht die Diagonale kreuzen. + \end{itemize} +\end{itemize} +\[C_0 = 1\qquad C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} = +\frac{1}{n + 1}\binom{2n}{n} = \frac{4n - 2}{n+1} C_{n-1} \sim \frac{4^n}{n^{3/2} \sqrt{\pi}}\] +\begin{itemize} + \item Formel $1$ ohne Division in \runtime{n^2}, Formel $2$ und $3$ in \runtime{n} +\end{itemize} + +\paragraph{\textsc{Catalan}-Convolution} +\begin{itemize} + \item Anzahl an Klammerausdrücken mit $n+k$ Klammerpaaren, die mit $\texttt{(}^k$ beginnen. +\end{itemize} +\[C^k_0 = 1\qquad C^k_n = \sum\limits_{\mathclap{a_0+a_1+\dots+a_k=n}} C_{a_0}C_{a_1}\cdots C_{a_k} = +\frac{k+1}{n+k+1}\binom{2n+k}{n} = \frac{(2n+k-1)(2n+k)}{n(n+k+1)} \cdot C^k_{n-1}\] + +\paragraph{\textsc{Euler}-Zahlen:} +$|~1~|~1~|~1,~1~|~1,~4,~1~|~1,~11,~11,~1~|~1,~26,~66,~26,~1~|$ + +Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Anstiegen. +Für die $n$-te Zahl gibt es $n$ mögliche Positionen zum Einfügen. +Dabei wird entweder ein Anstieg in zwei gesplitted oder ein Anstieg um $n$ ergänzt. +\[\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \quad +\eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1}\] +\[ +\eulerI{n}{k} = [x^k] + \left(\sum_{i=0}^\infty (i+1)^n x^i\right) + \left(\sum_{i=0}^\infty (-1)^i \binom{n+1}{i} x^i\right) +\] + +\paragraph{\textsc{Stirling}-Zahlen 1. Art:} +$|~1~|~0,~1~|~0,~1,~1~|~0,~2,~3,~1~|~0,~6,~11,~6,~1~|$ + +Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Zyklen. +Es gibt zwei Möglichkeiten für die $n$-te Zahl. Entweder sie bildet einen eigenen Zyklus, oder sie kann an jeder Position in jedem Zyklus einsortiert werden. +\[\stirlingI{0}{0} = 1 \qquad +\stirlingI{n}{0} = \stirlingI{0}{k} = 0 \qquad +\stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}\] +\[ +\stirlingI{n}{k} += [x^k]\prod_{i=0}^{n-1} (x+i) += n! [x^{n-k}] \frac{1}{k!} \left(\sum_{i=0}^\infty \frac{1}{i+1}x^i\right)^k +\] + +\paragraph{\textsc{Stirling}-Zahlen 2. Art:} +$|~1~|~0,~1~|~0,~1,~1~|~0,~1,~3,~1~|~0,~1,~7,~6,~1~|$ + +Die Anzahl der Möglichkeiten $n$ Elemente in $k$ nichtleere Teilmengen zu zerlegen. +Es gibt $k$ Möglichkeiten die $n$ in eine $n-1$-Partition einzuordnen. +Dazu kommt der Fall, dass die $n$ in ihrer eigenen Teilmenge (alleine) steht. +\[\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad +\stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1} +\] +\[ +\stirlingII{n}{k} += [x^k] + \left(\sum_{i=0}^\infty \frac{i^n}{i!}x^i\right) + \left(\sum_{i=0}^\infty \frac{(-1)^i}{i!}x^i\right) += n! [x^{n-k}] \frac{1}{k!} \left(\sum_{i=0}^\infty \frac{1}{(i+1)!}x^i\right)^k +\] + +\paragraph{\textsc{Bell}-Zahlen:} +$1,~1,~2,~5,~15,~52,~203,~877,~4140,~21147,~115975,~678570,~4213597$ + +Anzahl der Partitionen von $\{1, \ldots, n\}$. +Wie \textsc{Stirling}-Zahlen 2. Art ohne Limit durch $k$. +\[B_1 = 1 \qquad +B_n = \sum\limits_{k = 0}^{n - 1} B_k\binom{n-1}{k} += \sum\limits_{k = 0}^{n}\stirlingII{n}{k} += n! [x^n] e^{e^x-1} +\qquad +B_{p^m+n}\equiv m\cdot B_n + B_{n+1} \bmod{p}\] + +\paragraph{$\boldsymbol{k}$ Partitions:} +$|~1~|~0,~1~|~0,~1,~1~|~0,~1,~1,~1~|~0,~1,~2,~1,~1~|~0,~1,~2,~2,~1,~1~|~0,~1,~3,~3,~2,~1,~1~|$ + +Die Anzahl der Partitionen von $n$ in genau $k$ positive Summanden. +Die Anzahl der Partitionen von $n$ mit größtem Elementen $k$. +\begin{align*} + p_0(0)=1 \qquad p_k(n)&=0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0\\ + p_k(n)&= p_k(n-k) + p_{k-1}(n-1)\\ +\end{align*} + +\paragraph{Partitions:} +$1,~1,~2,~3,~5,~7,~11,~15,~22,~30,~42,~56,~77,~101,~135,~176,~231,~297,~385,~490,~627$ + +\begin{align*} + p(n)=\sum_{k=1}^{n} p_k(n)&=p_n(2n)=\sum\limits_{k=1}^\infty(-1)^{k+1}\bigg[p\bigg(n - \frac{k(3k-1)}{2}\bigg) + p\bigg(n - \frac{k(3k+1)}{2}\bigg)\bigg] \\ + p(n)&=[x^n] \left(\sum_{k=-\infty}^\infty (-1)^k x^{k(3k-1)/2}\right)^{-1} + \sim \frac{1}{4 \sqrt{3} n} \exp\left(\pi \sqrt{\frac{2n}{3}}\right) +\end{align*} +\begin{itemize} + \item in Formel $3$ kann abgebrochen werden wenn $\frac{k(3k-1)}{2} > n$. + $\rightarrow$ \runtime{n \sqrt{n}} + \item Die Anzahl der Partitionen von $n$ in bis zu $k$ positive Summanden ist $\sum\limits_{i=0}^{k}p_i(n)=p_k(n+k)$. +\end{itemize} + +\subsection{The Twelvefold Way \textnormal{(verteile $n$ Bälle auf $k$ Boxen)}} +\input{math/tables/twelvefold} + +\subsection{Platonische Körper} +\input{math/tables/platonic} + +\input{math/tables/probability} + +\subsection{Satz von \textsc{Sprague-Grundy}} +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\} +\] +$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)$. + +\subsection{Nim-Spiele} +\begin{itemize} + \item[\ding{182}] letzter gewinnt (normal) + \item[\ding{183}] letzter verliert +\end{itemize} +\input{math/tables/nim} + +\subsection{Verschiedenes} +\input{math/tables/stuff} + +\begin{algorithm}{Div Sum} + \method{divSum}{berechnet $\sum_{i=0}^{n-1} \left\lfloor \frac{a\cdot i + b}{m} \right\rfloor$}{\log(n)} + \textbf{Wichtig:} $b$ darf nicht negativ sein! + \sourcecode{math/divSum.cpp} +\end{algorithm} + +\begin{algorithm}{Min Mod} + \begin{methods} + \method{firstVal}{berechnet den ersten Wert von $0,\ a, \ldots,\ a \cdot i \bmod{m}$,}{\log(m)} + \method{}{der in $[l, r]$ liegt. Gibt $-1$ zurück, falls er nicht existiert.}{} + \method{minMod}{berechnet das Minimum von $(a \cdot i + b) \bmod{m}$ für $i \in [0, n)$}{\log(m)} + \end{methods} + \textbf{Wichtig:} $0 \leq a, b, l, r < m$ + \sourcecode{math/minMod.cpp} +\end{algorithm} + +\subsection{Reihen} +\input{math/tables/series} + +\subsection{Wichtige Zahlen} +\input{math/tables/prime-composite} + +\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ } +\method{recover}{findet $x$ und $y$ für $c=x\*y^{-1}\bmod m$}{\log(m)} +\textbf{WICHTIG:} $x$ und $y$ müssen kleiner als $\sqrt{\nicefrac{m}{2}}$ sein! +\sourcecode{math/recover.cpp} + +\optional{ +\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$} +\begin{methods} + \method{init}{berechnet $\pi$ bis $N$}{N\*\log(\log(N))} + \method{phi}{zählt zu $p_i$ teilerfremde Zahlen $\leq n$ für alle $i \leq k$}{???} + \method{pi}{zählt Primzahlen $\leq n$ ($n < N^2$)}{n^{2/3}} +\end{methods} +\sourcecode{math/piLehmer.cpp} + +\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$} +\sourcecode{math/piLegendre.cpp} +} + +\begin{algorithm}[optional]{Big Integers} + \sourcecode{math/bigint.cpp} +\end{algorithm} diff --git a/content/math/matrixPower.cpp b/content/math/matrixPower.cpp index d981e6e..d80dac6 100644 --- a/content/math/matrixPower.cpp +++ b/content/math/matrixPower.cpp @@ -1,14 +1,14 @@ vector<mat> pows; void precalc(mat m) { - pows = {mat(sz(m.m), 1), m}; - for (int i = 1; i < 60; i++) pows.push_back(pows[i] * pows[i]); + pows = {m}; + for (int i = 0; i < 60; i++) pows.push_back(pows[i] * pows[i]); } auto calc(ll b, vector<ll> v) { - for (ll i = 1; b > 0; i++) { + for (ll i = 0; b > 0; i++) { if (b & 1) v = pows[i] * v; - b /= 2; + b >>= 1; } return v; } diff --git a/content/math/modExp.cpp b/content/math/modExp.cpp deleted file mode 100644 index 2329a94..0000000 --- a/content/math/modExp.cpp +++ /dev/null @@ -1,6 +0,0 @@ -ll powMod(ll a, ll b, ll n) { - if(b == 0) return 1; - if(b == 1) return a % n; - if(b & 1) return (powMod(a, b - 1, n) * a) % n; - else return powMod((a * a) % n, b / 2, n); -} diff --git a/content/math/permIndex.cpp b/content/math/permIndex.cpp index 4cffc12..563b33a 100644 --- a/content/math/permIndex.cpp +++ b/content/math/permIndex.cpp @@ -1,12 +1,12 @@ ll permIndex(vector<ll> v) { Tree<ll> t; - reverse(all(v)); + ranges::reverse(v); for (ll& x : v) { t.insert(x); x = t.order_of_key(x); } ll res = 0; - for (int i = sz(v); i > 0; i--) { + for (int i = ssize(v); i > 0; i--) { res = res * i + v[i - 1]; } return res; diff --git a/content/math/piLegendre.cpp b/content/math/piLegendre.cpp index 21b974b..6401a4f 100644 --- a/content/math/piLegendre.cpp +++ b/content/math/piLegendre.cpp @@ -1,23 +1,23 @@ -constexpr ll cache = 500; // requires O(cache^3)
-vector<vector<ll>> memo(cache * cache, vector<ll>(cache));
-
-ll pi(ll n);
-
-ll phi(ll n, ll k) {
- if (n <= 1 || k < 0) return 0;
- if (n <= primes[k]) return n - 1;
- if (n < N && primes[k] * primes[k] > n) return n - pi(n) + k;
- bool ok = n < cache * cache;
- if (ok && memo[n][k] > 0) return memo[n][k];
- ll res = n/primes[k] - phi(n/primes[k], k - 1) + phi(n, k - 1);
- if (ok) memo[n][k] = res;
- return res;
-}
-
-ll pi(ll n) {
- if (n < N) { // implement this as O(1) lookup for speedup!
- return distance(primes.begin(), upper_bound(all(primes), n));
- } else {
- ll k = pi(sqrtl(n) + 1);
- return n - phi(n, k) + k;
-}}
+constexpr ll cache = 500; // requires O(cache^3) +vector<vector<ll>> memo(cache * cache, vector<ll>(cache)); + +ll pi(ll n); + +ll phi(ll n, ll k) { + if (n <= 1 || k < 0) return 0; + if (n <= primes[k]) return n - 1; + if (n < N && primes[k] * primes[k] > n) return n - pi(n) + k; + bool ok = n < cache * cache; + if (ok && memo[n][k] > 0) return memo[n][k]; + ll res = n/primes[k] - phi(n/primes[k], k - 1) + phi(n, k - 1); + if (ok) memo[n][k] = res; + return res; +} + +ll pi(ll n) { + if (n < N) { // implement this as O(1) lookup for speedup! + return ranges::upper_bound(primes, n) - begin(primes); + } else { + ll k = pi(sqrtl(n) + 1); + return n - phi(n, k) + k; +}} diff --git a/content/math/piLehmer.cpp b/content/math/piLehmer.cpp index adef16d..83e1b95 100644 --- a/content/math/piLehmer.cpp +++ b/content/math/piLehmer.cpp @@ -1,52 +1,52 @@ -constexpr ll cacheA = 2 * 3 * 5 * 7 * 11 * 13 * 17;
-constexpr ll cacheB = 7;
-ll memoA[cacheA + 1][cacheB + 1];
-ll memoB[cacheB + 1];
-ll memoC[N];
-
-void init() {
- primeSieve(); // @\sourceref{math/primeSieve.cpp}@
- for (ll i = 1; i < N; i++) {
- memoC[i] = memoC[i - 1];
- if (isPrime(i)) memoC[i]++;
- }
- memoB[0] = 1;
- for(ll i = 0; i <= cacheA; i++) memoA[i][0] = i;
- for(ll i = 1; i <= cacheB; i++) {
- memoB[i] = primes[i - 1] * memoB[i - 1];
- for(ll j = 1; j <= cacheA; j++) {
- memoA[j][i] = memoA[j][i - 1] - memoA[j /
- primes[i - 1]][i - 1];
-}}}
-
-ll phi(ll n, ll k) {
- if(k == 0) return n;
- if(k <= cacheB)
- return memoA[n % memoB[k]][k] +
- (n / memoB[k]) * memoA[memoB[k]][k];
- if(n <= primes[k - 1]*primes[k - 1]) return memoC[n] - k + 1;
- if(n <= primes[k - 1]*primes[k - 1]*primes[k - 1] && n < N) {
- ll b = memoC[(ll)sqrtl(n)];
- ll res = memoC[n] - (b + k - 2) * (b - k + 1) / 2;
- for(ll i = k; i < b; i++) res += memoC[n / primes[i]];
- return res;
- }
- return phi(n, k - 1) - phi(n / primes[k - 1], k - 1);
-}
-
-ll pi(ll n) {
- if (n < N) return memoC[n];
- ll a = pi(sqrtl(sqrtl(n)));
- ll b = pi(sqrtl(n));
- ll c = pi(cbrtl(n));
- ll res = phi(n, a) + (b + a - 2) * (b - a + 1) / 2;
- for (ll i = a; i < b; i++) {
- ll w = n / primes[i];
- res -= pi(w);
- if (i > c) continue;
- ll bi = pi(sqrtl(w));
- for (ll j = i; j < bi; j++) {
- res -= pi(w / primes[j]) - j;
- }}
- return res;
-}
+constexpr ll cacheA = 2 * 3 * 5 * 7 * 11 * 13 * 17; +constexpr ll cacheB = 7; +ll memoA[cacheA + 1][cacheB + 1]; +ll memoB[cacheB + 1]; +ll memoC[N]; + +void init() { + primeSieve(); // @\sourceref{math/primeSieve.cpp}@ + for (ll i = 1; i < N; i++) { + memoC[i] = memoC[i - 1]; + if (isPrime(i)) memoC[i]++; + } + memoB[0] = 1; + for(ll i = 0; i <= cacheA; i++) memoA[i][0] = i; + for(ll i = 1; i <= cacheB; i++) { + memoB[i] = primes[i - 1] * memoB[i - 1]; + for(ll j = 1; j <= cacheA; j++) { + memoA[j][i] = memoA[j][i - 1] - memoA[j / + primes[i - 1]][i - 1]; +}}} + +ll phi(ll n, ll k) { + if(k == 0) return n; + if(k <= cacheB) + return memoA[n % memoB[k]][k] + + (n / memoB[k]) * memoA[memoB[k]][k]; + if(n <= primes[k - 1]*primes[k - 1]) return memoC[n] - k + 1; + if(n <= primes[k - 1]*primes[k - 1]*primes[k - 1] && n < N) { + ll b = memoC[(ll)sqrtl(n)]; + ll res = memoC[n] - (b + k - 2) * (b - k + 1) / 2; + for(ll i = k; i < b; i++) res += memoC[n / primes[i]]; + return res; + } + return phi(n, k - 1) - phi(n / primes[k - 1], k - 1); +} + +ll pi(ll n) { + if (n < N) return memoC[n]; + ll a = pi(sqrtl(sqrtl(n))); + ll b = pi(sqrtl(n)); + ll c = pi(cbrtl(n)); + ll res = phi(n, a) + (b + a - 2) * (b - a + 1) / 2; + for (ll i = a; i < b; i++) { + ll w = n / primes[i]; + res -= pi(w); + if (i > c) continue; + ll bi = pi(sqrtl(w)); + for (ll j = i; j < bi; j++) { + res -= pi(w / primes[j]) - j; + }} + return res; +} diff --git a/content/math/polynomial.cpp b/content/math/polynomial.cpp index 84f3aaa..12a4fd7 100644 --- a/content/math/polynomial.cpp +++ b/content/math/polynomial.cpp @@ -4,15 +4,15 @@ struct poly { poly(int deg = 0) : data(1 + deg) {} poly(initializer_list<ll> _data) : data(_data) {} - int size() const {return sz(data);} + int size() const { return ssize(data); } void trim() { for (ll& x : data) x = (x % mod + mod) % mod; while (size() > 1 && data.back() == 0) data.pop_back(); } - ll& operator[](int x) {return data[x];} - const ll& operator[](int x) const {return data[x];} + ll& operator[](int x) { return data[x]; } + const ll& operator[](int x) const { return data[x]; } ll operator()(int x) const { ll res = 0; diff --git a/content/math/primeSieve.cpp b/content/math/primeSieve.cpp index 1b0f514..2b2bf26 100644 --- a/content/math/primeSieve.cpp +++ b/content/math/primeSieve.cpp @@ -8,7 +8,7 @@ bool isPrime(ll x) { } void primeSieve() { - for (ll i = 3; i < N; i += 2) {// i * i < N reicht für isPrime + for (ll i = 3; i < N; i += 2) { // i * i < N reicht für isPrime if (!isNotPrime[i / 2]) { primes.push_back(i); // optional for (ll j = i * i; j < N; j+= 2 * i) { diff --git a/content/math/recover.cpp b/content/math/recover.cpp index 1a593f0..a4c22aa 100644 --- a/content/math/recover.cpp +++ b/content/math/recover.cpp @@ -1,4 +1,4 @@ -ll sq(ll x) {return x*x;} +ll sq(ll x) { return x*x; } array<ll, 2> recover(ll c, ll m) { array<ll, 2> u = {m, 0}, v = {c, 1}; diff --git a/content/math/rho.cpp b/content/math/rho.cpp index ad640cd..c7f7a70 100644 --- a/content/math/rho.cpp +++ b/content/math/rho.cpp @@ -2,7 +2,7 @@ using lll = __int128; ll rho(ll n) { // Findet Faktor < n, nicht unbedingt prim. if (n % 2 == 0) return 2; ll x = 0, y = 0, prd = 2, i = n/2 + 7; - auto f = [&](lll c){return (c * c + i) % n;}; + auto f = [&](lll c) { return (c * c + i) % n; }; for (ll t = 30; t % 40 || gcd(prd, n) == 1; t++) { if (x == y) x = ++i, y = f(x); if (ll q = (lll)prd * abs(x-y) % n; q) prd = q; @@ -13,7 +13,7 @@ ll rho(ll n) { // Findet Faktor < n, nicht unbedingt prim. void factor(ll n, map<ll, int>& facts) { if (n == 1) return; - if (isPrime(n)) {facts[n]++; return;} + if (isPrime(n)) { facts[n]++; return; } ll f = rho(n); factor(n / f, facts); factor(f, facts); } diff --git a/content/math/shortModInv.cpp b/content/math/shortModInv.cpp index cf91ca0..7d3002c 100644 --- a/content/math/shortModInv.cpp +++ b/content/math/shortModInv.cpp @@ -1,3 +1,3 @@ ll multInv(ll x, ll m) { // x^{-1} mod m - return 1 < x ? m - multInv(m % x, x) * m / x : 1; + return 1 < (x %= m) ? m - multInv(m, x) * m / x : 1; } diff --git a/content/math/simpson.cpp b/content/math/simpson.cpp index 7f237a4..da9c002 100644 --- a/content/math/simpson.cpp +++ b/content/math/simpson.cpp @@ -1,4 +1,4 @@ -//double f(double x) {return x;} +//double f(double x) { return x; } double simps(double a, double b) { return (f(a) + 4.0 * f((a + b) / 2.0) + f(b)) * (b - a) / 6.0; diff --git a/content/math/sqrtModCipolla.cpp b/content/math/sqrtModCipolla.cpp index 1fac0c5..c062646 100644 --- a/content/math/sqrtModCipolla.cpp +++ b/content/math/sqrtModCipolla.cpp @@ -1,4 +1,4 @@ -ll sqrtMod(ll a, ll p) {// teste mit legendre ob lösung existiert +ll sqrtMod(ll a, ll p) {// teste mit Legendre ob Lösung existiert if (a < 2) return a; ll t = 0; while (legendre((t*t-4*a) % p, p) >= 0) t = rng() % p; 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/nim.tex b/content/math/tables/nim.tex index 5a196e5..3c36bbb 100644 --- a/content/math/tables/nim.tex +++ b/content/math/tables/nim.tex @@ -1,3 +1,4 @@ +In jedem Zug, wähle $m \in M$ und nimm $m$ Objekte. \begin{expandtable} \begin{tabularx}{\linewidth}{|p{0.37\linewidth}|X|} \hline @@ -84,14 +85,12 @@ $\mathit{SG}_n = n - 1$, falls $n \equiv 0 \bmod 4$\\ \hline - \textsc{Kayles}' Nim:\newline - Zwei mögliche Züge:\newline - 1) Nehme $1$ oder $2$.\newline - 2) Teile Stapel in zwei Stapel (mit Entnahme).& + Kayles:\newline + Nimm 1 oder 2, dann teile den Stapel optional in zwei Stapel.& Berechne $\mathit{SG}_n$ für kleine $n$ rekursiv.\newline $n \in [72,83]: \quad 4, 1, 2, 8, 1, 4, 7, 2, 1, 8, 2, 7$\newline Periode ab $n = 72$ der Länge $12$.\\ \hline \end{tabularx} \end{expandtable} -
\ No newline at end of file + diff --git a/content/math/tables/prime-composite.tex b/content/math/tables/prime-composite.tex new file mode 100644 index 0000000..b8adadf --- /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} & \# Prime \\ + & & & $<$ & $>$ & & Factors \\ + \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 & 15 \\ + \hline +\end{tabularx} +\end{expandtable} diff --git a/content/math/transforms/andTransform.cpp b/content/math/transforms/andTransform.cpp index 93a323a..87bae0b 100644 --- a/content/math/transforms/andTransform.cpp +++ b/content/math/transforms/andTransform.cpp @@ -1,8 +1,8 @@ void fft(vector<ll>& a, bool inv = false) { - int n = sz(a); + int n = ssize(a); for (int s = 1; s < n; s *= 2) { for (int i = 0; i < n; i += 2 * s) { for (int j = i; j < i + s; j++) { - ll& u = a[j], &v = a[j + s]; + ll &u = a[j], &v = a[j + s]; u = inv ? u - v : u + v; }}}} diff --git a/content/math/transforms/bitwiseTransforms.cpp b/content/math/transforms/bitwiseTransforms.cpp index fbe3792..c0f6e50 100644 --- a/content/math/transforms/bitwiseTransforms.cpp +++ b/content/math/transforms/bitwiseTransforms.cpp @@ -1,9 +1,9 @@ void bitwiseConv(vector<ll>& a, bool inv = false) { - int n = sz(a); + int n = ssize(a); for (int s = 1; s < n; s *= 2) { for (int i = 0; i < n; i += 2 * s) { for (int j = i; j < i + s; j++) { - ll& u = a[j], &v = a[j + s]; + ll &u = a[j], &v = a[j + s]; u = inv ? u - v : u + v; // AND //v = inv ? v - u : v + u; // OR //tie(u, v) = pair(u + v, u - v); // XOR diff --git a/content/math/transforms/fft.cpp b/content/math/transforms/fft.cpp index 2bd95b2..1f80e36 100644 --- a/content/math/transforms/fft.cpp +++ b/content/math/transforms/fft.cpp @@ -1,7 +1,7 @@ using cplx = complex<double>; void fft(vector<cplx>& a, bool inv = false) { - int n = sz(a); + int n = ssize(a); for (int i = 0, j = 1; j < n - 1; ++j) { for (int k = n >> 1; k > (i ^= k); k >>= 1); if (j < i) swap(a[i], a[j]); diff --git a/content/math/transforms/fftMul.cpp b/content/math/transforms/fftMul.cpp index 660ed79..da6a538 100644 --- a/content/math/transforms/fftMul.cpp +++ b/content/math/transforms/fftMul.cpp @@ -1,8 +1,8 @@ vector<cplx> mul(vector<ll>& a, vector<ll>& b) { - int n = 1 << (__lg(sz(a) + sz(b) - 1) + 1); - vector<cplx> c(all(a)), d(n); + int n = 1 << (__lg(ssize(a) + ssize(b) - 1) + 1); + vector<cplx> c(begin(a), end(a)), d(n); c.resize(n); - for (int i = 0; i < sz(b); i++) c[i] = {real(c[i]), b[i]}; + for (int i = 0; i < ssize(b); i++) c[i] = {real(c[i]), b[i]}; fft(c); for (int i = 0; i < n; i++) { int j = (n - i) & (n - 1); diff --git a/content/math/transforms/multiplyBitwise.cpp b/content/math/transforms/multiplyBitwise.cpp index f7cf169..5275b8c 100644 --- a/content/math/transforms/multiplyBitwise.cpp +++ b/content/math/transforms/multiplyBitwise.cpp @@ -1,5 +1,5 @@ vector<ll> mul(vector<ll> a, vector<ll> b) { - int n = 1 << (__lg(2 * max(sz(a), sz(b)) - 1)); + int n = 1 << (__lg(2 * max(ssize(a), ssize(b)) - 1)); a.resize(n), b.resize(n); bitwiseConv(a), bitwiseConv(b); for (int i=0; i<n; i++) a[i] *= b[i]; // MOD? diff --git a/content/math/transforms/multiplyFFT.cpp b/content/math/transforms/multiplyFFT.cpp index 0022d1f..963be94 100644 --- a/content/math/transforms/multiplyFFT.cpp +++ b/content/math/transforms/multiplyFFT.cpp @@ -1,6 +1,6 @@ vector<ll> mul(vector<ll>& a, vector<ll>& b) { - int n = 1 << (__lg(sz(a) + sz(b) - 1) + 1); - vector<cplx> a2(all(a)), b2(all(b)); + int n = 1 << (__lg(ssize(a) + ssize(b) - 1) + 1); + vector<cplx> a2(begin(a), end(a)), b2(begin(b), end(b)); a2.resize(n), b2.resize(n); fft(a2), fft(b2); for (int i=0; i<n; i++) a2[i] *= b2[i]; diff --git a/content/math/transforms/multiplyNTT.cpp b/content/math/transforms/multiplyNTT.cpp index 806d124..d234ce3 100644 --- a/content/math/transforms/multiplyNTT.cpp +++ b/content/math/transforms/multiplyNTT.cpp @@ -1,5 +1,5 @@ vector<ll> mul(vector<ll> a, vector<ll> b) { - int n = 1 << (__lg(sz(a) + sz(b) - 1) + 1); + int n = 1 << bit_width(size(a) + size(b) - 1); a.resize(n), b.resize(n); ntt(a), ntt(b); for (int i=0; i<n; i++) a[i] = a[i] * b[i] % mod; diff --git a/content/math/transforms/ntt.cpp b/content/math/transforms/ntt.cpp index ca605d3..fc7874e 100644 --- a/content/math/transforms/ntt.cpp +++ b/content/math/transforms/ntt.cpp @@ -1,7 +1,7 @@ constexpr ll mod = 998244353, root = 3; void ntt(vector<ll>& a, bool inv = false) { - int n = sz(a); + int n = ssize(a); auto b = a; ll r = inv ? powMod(root, mod - 2, mod) : root; diff --git a/content/math/transforms/orTransform.cpp b/content/math/transforms/orTransform.cpp index 60b4426..1833ac5 100644 --- a/content/math/transforms/orTransform.cpp +++ b/content/math/transforms/orTransform.cpp @@ -1,8 +1,8 @@ void fft(vector<ll>& a, bool inv = false) { - int n = sz(a); + int n = ssize(a); for (int s = 1; s < n; s *= 2) { for (int i = 0; i < n; i += 2 * s) { for (int j = i; j < i + s; j++) { - ll& u = a[j], &v = a[j + s]; + ll &u = a[j], &v = a[j + s]; v = inv ? v - u : v + u; }}}} diff --git a/content/math/transforms/seriesOperations.cpp b/content/math/transforms/seriesOperations.cpp index d3e3072..cfac7b9 100644 --- a/content/math/transforms/seriesOperations.cpp +++ b/content/math/transforms/seriesOperations.cpp @@ -17,7 +17,7 @@ vector<ll> poly_inv(const vector<ll>& a, int n) { // a[0] == 1 } vector<ll> poly_deriv(vector<ll> a) { - for (int i = 1; i < sz(a); i++) + for (int i = 1; i < ssize(a); i++) a[i-1] = a[i] * i % mod; a.pop_back(); return a; @@ -25,11 +25,11 @@ vector<ll> poly_deriv(vector<ll> a) { vector<ll> poly_integr(vector<ll> a) { static vector<ll> inv = {0, 1}; - for (static int i = 2; i <= sz(a); i++) + for (static int i = 2; i <= ssize(a); i++) inv.push_back(mod - mod / i * inv[mod % i] % mod); a.push_back(0); - for (int i = sz(a) - 1; i > 0; i--) + for (int i = ssize(a) - 1; i > 0; i--) a[i] = a[i-1] * inv[i] % mod; a[0] = 0; return a; @@ -46,7 +46,7 @@ vector<ll> poly_exp(vector<ll> a, int n) { // a[0] == 0 for (int len = 1; len < n; len *= 2) { vector<ll> p = poly_log(q, 2*len); for (int i = 0; i < 2*len; i++) - p[i] = (mod - p[i] + (i < sz(a) ? a[i] : 0)) % mod; + p[i] = (mod - p[i] + (i < ssize(a) ? a[i] : 0)) % mod; vector<ll> q2 = q; q2.resize(2*len); ntt(p), ntt(q2); diff --git a/content/math/transforms/xorTransform.cpp b/content/math/transforms/xorTransform.cpp index f9d1d82..aa3db8d 100644 --- a/content/math/transforms/xorTransform.cpp +++ b/content/math/transforms/xorTransform.cpp @@ -1,9 +1,9 @@ void fft(vector<ll>& a, bool inv = false) { - int n = sz(a); + int n = ssize(a); for (int s = 1; s < n; s *= 2) { for (int i = 0; i < n; i += 2 * s) { for (int j = i; j < i + s; j++) { - ll& u = a[j], &v = a[j + s]; + ll &u = a[j], &v = a[j + s]; tie(u, v) = pair(u + v, u - v); }}} if (inv) for (ll& x : a) x /= n; |