diff options
Diffstat (limited to 'math')
| -rw-r--r-- | math/binomial1.cpp | 3 | ||||
| -rw-r--r-- | math/chineseRemainder.cpp | 26 | ||||
| -rw-r--r-- | math/extendedEuclid.cpp | 9 | ||||
| -rw-r--r-- | math/math.tex | 187 | ||||
| -rw-r--r-- | math/multInv.cpp | 7 | ||||
| -rw-r--r-- | math/shortModInv.cpp | 4 | ||||
| -rw-r--r-- | math/transforms/seriesOperations.cpp | 41 |
7 files changed, 138 insertions, 139 deletions
diff --git a/math/binomial1.cpp b/math/binomial1.cpp index 02b27e3..dab20b3 100644 --- a/math/binomial1.cpp +++ b/math/binomial1.cpp @@ -2,8 +2,7 @@ ll calc_binom(ll n, ll k) { if (k > n) return 0; ll r = 1; for (ll d = 1; d <= k; d++) {// Reihenfolge => Teilbarkeit - r *= n--; - r /= d; + r *= n--, r /= d; } return r; } diff --git a/math/chineseRemainder.cpp b/math/chineseRemainder.cpp index a1aa480..ccbc5dc 100644 --- a/math/chineseRemainder.cpp +++ b/math/chineseRemainder.cpp @@ -1,14 +1,14 @@ -struct CRT{ - using lll = __int128_t; - lll M = 1, sol = 0; // Solution unique modulo M - bool hasSol = true; +struct CRT { + using lll = __int128; + lll M = 1, sol = 0; // Solution unique modulo M + bool hasSol = true; - // Adds congruence x = a (mod m) - void add(ll a, ll m){ - ll s, t, d = extendedEuclid(M, m, s, t); - if((a - sol) % d != 0) hasSol = false; - lll z = M/d * s; - M *= m/d; - sol = (z % M * (a-sol) % M + sol + M) % M; - } -};
\ No newline at end of file + // Adds congruence x = a (mod m) + void add(ll a, ll m) { + auto [d, s, t] = extendedEuclid(M, m); + if((a - sol) % d != 0) hasSol = false; + lll z = M/d * s; + M *= m/d; + sol = (z % M * (a-sol) % M + sol + M) % M; + } +}; diff --git a/math/extendedEuclid.cpp b/math/extendedEuclid.cpp index d016a63..ecf4a16 100644 --- a/math/extendedEuclid.cpp +++ b/math/extendedEuclid.cpp @@ -1,7 +1,6 @@ // a*x + b*y = ggt(a, b) -ll extendedEuclid(ll a, ll b, ll& x, ll& y) { - if (a == 0) {x = 0; y = 1; return b;} - ll x1, y1, d = extendedEuclid(b % a, a, x1, y1); - x = y1 - (b / a) * x1; y = x1; - return d; +array<ll, 3> extendedEuclid(ll a, ll b) { + if (a == 0) return {b, 0, 1}; + auto [d, x, y] = extendedEuclid(b % a, a); + return {d, y - (b / a) * x, x}; } diff --git a/math/math.tex b/math/math.tex index bae7bff..a4cbde8 100644 --- a/math/math.tex +++ b/math/math.tex @@ -1,5 +1,12 @@ \section{Mathe}
+\begin{algorithm}{Zykel Erkennung}
+ \begin{methods}
+ \method{cycleDetection}{findet Zyklus von $x_0$ und Länge in $f$}{b+l}
+ \end{methods}
+ \sourcecode{math/cycleDetection.cpp}
+\end{algorithm}
+
\begin{algorithm}{Longest Increasing Subsequence}
\begin{itemize}
\item \code{lower\_bound} $\Rightarrow$ streng monoton
@@ -7,14 +14,6 @@ \end{itemize}
\sourcecode{math/longestIncreasingSubsequence.cpp}
\end{algorithm}
-\columnbreak
-
-\begin{algorithm}{Zykel Erkennung}
- \begin{methods}
- \method{cycleDetection}{findet Zyklus von $x_0$ und Länge in $f$}{b+l}
- \end{methods}
- \sourcecode{math/cycleDetection.cpp}
-\end{algorithm}
\begin{algorithm}{Permutationen}
\begin{methods}
@@ -49,21 +48,20 @@ \begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus}
\runtime{\log(a) + \log(b)}
- \sourcecode{math/gcd-lcm.cpp}
\sourcecode{math/extendedEuclid.cpp}
\end{algorithm}
-\subsection{Multiplikatives Inverses von $\boldsymbol{n}$ in $\boldsymbol{\mathbb{Z}/p\mathbb{Z}}$}
-\textbf{Falls $\boldsymbol{p}$ prim:}\quad $x^{-1} \equiv x^{p-2} \bmod p$
+\subsection{Multiplikatives Inverses von $\boldsymbol{x}$ in $\boldsymbol{\mathbb{Z}/m\mathbb{Z}}$}
+\textbf{Falls $\boldsymbol{m}$ prim:}\quad $x^{-1} \equiv x^{m-2} \bmod m$
-\textbf{Falls $\boldsymbol{\ggT(n, p) = 1}$:}
+\textbf{Falls $\boldsymbol{\ggT(x, m) = 1}$:}
\begin{itemize}
\item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit
- $\alpha n + \beta p = 1$.
- \item Nach Kongruenz gilt $\alpha n + \beta p \equiv \alpha n \equiv 1 \bmod p$.
- \item $n^{-1} :\equiv \alpha \bmod p$
+ $\alpha x + \beta m = 1$.
+ \item Nach Kongruenz gilt $\alpha x + \beta m \equiv \alpha x \equiv 1 \bmod m$.
+ \item $x^{-1} :\equiv \alpha \bmod m$
\end{itemize}
-\textbf{Sonst $\boldsymbol{\ggT(n, p) > 1}$:}\quad Es existiert kein $x^{-1}$.
+\textbf{Sonst $\boldsymbol{\ggT(x, m) > 1}$:}\quad Es existiert kein $x^{-1}$.
% \sourcecode{math/multInv.cpp}
\sourcecode{math/shortModInv.cpp}
@@ -126,19 +124,12 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/divisors.cpp}
\end{algorithm}
-\begin{algorithm}{Primitivwurzeln}
- \begin{itemize}
- \item Primitivwurzel modulo $n$ existiert $\Leftrightarrow$ $n \in \{2,\ 4,\ p^\alpha,\ 2\cdot p^\alpha \mid\ 2 < p \in \mathbb{P},\ \alpha \in \mathbb{N}\}$
- \item es existiert entweder keine oder $\varphi(\varphi(n))$ inkongruente Primitivwurzeln
- \item Sei $g$ Primitivwurzel modulo $n$.
- Dann gilt:\newline
- Das kleinste $k$, sodass $g^k \equiv 1 \bmod n$, ist $k = \varphi(n)$.
- \end{itemize}
- \begin{methods}
- \method{isPrimitive}{prüft ob $g$ eine Primitivwurzel ist}{\log(\varphi(n))\*\log(n)}
- \method{findPrimitive}{findet Primitivwurzel (oder -1)}{\abs{ans}\*\log(\varphi(n))\*\log(n)}
- \end{methods}
- \sourcecode{math/primitiveRoot.cpp}
+\begin{algorithm}{Numerisch Extremstelle bestimmen}
+ \sourcecode{math/goldenSectionSearch.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Numerisch Integrieren, Simpsonregel}
+ \sourcecode{math/simpson.cpp}
\end{algorithm}
\begin{algorithm}{Diskreter Logarithmus}
@@ -156,6 +147,21 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/discreteNthRoot.cpp}
\end{algorithm}
+\begin{algorithm}{Primitivwurzeln}
+ \begin{itemize}
+ \item Primitivwurzel modulo $n$ existiert $\Leftrightarrow$ $n \in \{2,\ 4,\ p^\alpha,\ 2\cdot p^\alpha \mid\ 2 < p \in \mathbb{P},\ \alpha \in \mathbb{N}\}$
+ \item es existiert entweder keine oder $\varphi(\varphi(n))$ inkongruente Primitivwurzeln
+ \item Sei $g$ Primitivwurzel modulo $n$.
+ Dann gilt:\newline
+ Das kleinste $k$, sodass $g^k \equiv 1 \bmod n$, ist $k = \varphi(n)$.
+ \end{itemize}
+ \begin{methods}
+ \method{isPrimitive}{prüft ob $g$ eine Primitivwurzel ist}{\log(\varphi(n))\*\log(n)}
+ \method{findPrimitive}{findet Primitivwurzel (oder -1)}{\abs{ans}\*\log(\varphi(n))\*\log(n)}
+ \end{methods}
+ \sourcecode{math/primitiveRoot.cpp}
+\end{algorithm}
+
\begin{algorithm}{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$.
@@ -190,7 +196,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \end{itemize}
\end{algorithm}
-
\begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}}
\begin{itemize}
\item Bis $10^8$ in unter 64MB Speicher (lange Berechnung)
@@ -221,33 +226,25 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: %\sourcecode{math/mobius.cpp}
\end{algorithm}
-%\columnbreak
-%\subsection{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion}
-%\begin{itemize}
-% \item Zählt die relativ primen Zahlen $\leq n$.
-%
-% \item Multiplikativ:
-% $\gcd(a,b) = 1 \Longrightarrow \varphi(a) \cdot \varphi(b) = \varphi(ab)$
-%
-% \item $p$ prim, $k \in \mathbb{N}$:
-% $~\varphi(p^k) = p^k - p^{k - 1}$
-%
-% \item \textbf{\textsc{Euler}'s Theorem:}
-% Für $b \geq \varphi(c)$ gilt: $a^b \equiv a^{b \bmod \varphi(c) + \varphi(c)} \pmod{c}$. Darüber hinaus gilt: $\gcd(a, c) = 1 \Leftrightarrow a^b \equiv a^{b \bmod \varphi(c)} \pmod{c}$.
-% Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}:
-% $a^{m} \equiv a \pmod{m}$
-%\end{itemize}
-%\sourcecode{math/phi.cpp}
-
-
-\begin{algorithm}{Numerisch Extremstelle bestimmen}
- \sourcecode{math/goldenSectionSearch.cpp}
-\end{algorithm}
-
-
-\begin{algorithm}{Numerisch Integrieren, Simpsonregel}
- \sourcecode{math/simpson.cpp}
-\end{algorithm}
+\optional{
+\columnbreak
+\subsection{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion}
+\begin{itemize}
+ \item Zählt die relativ primen Zahlen $\leq n$.
+
+ \item Multiplikativ:
+ $\gcd(a,b) = 1 \Longrightarrow \varphi(a) \cdot \varphi(b) = \varphi(ab)$
+
+ \item $p$ prim, $k \in \mathbb{N}$:
+ $~\varphi(p^k) = p^k - p^{k - 1}$
+
+ \item \textbf{\textsc{Euler}'s Theorem:}
+ Für $b \geq \varphi(c)$ gilt: $a^b \equiv a^{b \bmod \varphi(c) + \varphi(c)} \pmod{c}$. Darüber hinaus gilt: $\gcd(a, c) = 1 \Leftrightarrow a^b \equiv a^{b \bmod \varphi(c)} \pmod{c}$.
+ Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}:
+ $a^{m} \equiv a \pmod{m}$
+\end{itemize}
+\sourcecode{math/phi.cpp}
+}
\begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}
Multipliziert Polynome $A$ und $B$.
@@ -264,21 +261,52 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: %\textcolor{safeOrange}{$\blacksquare$} NTT code, %\textcolor{safeGreen}{$\blacksquare$} FFT code
\sourcecode{math/transforms/fft.cpp}
\sourcecode{math/transforms/ntt.cpp}
+ \columnbreak
\sourcecode{math/transforms/bitwiseTransforms.cpp}
Multiplikation mit 2 transforms statt 3: (nur benutzten wenn nötig!)
\sourcecode{math/transforms/fftMul.cpp}
\end{algorithm}
-\subsection{LGS über $\boldsymbol{\mathbb{R}}$}
-\method{gauss}{löst LGS}{n^3}
-\sourcecode{math/gauss.cpp}
+\begin{algorithm}{Operations on Formal Power Series}
+ \sourcecode{math/transforms/seriesOperations.cpp}
+\end{algorithm}
\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$}
\method{gauss}{löst LGS}{n^3}
\sourcecode{math/lgsFp.cpp}
-\columnbreak
+\subsection{LGS über $\boldsymbol{\mathbb{R}}$}
+\method{gauss}{löst LGS}{n^3}
+\sourcecode{math/gauss.cpp}
+
+\begin{algorithm}{\textsc{Legendre}-Symbol}
+ Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$:
+ \begin{align*}
+ \legendre{a}{p} &=
+ \begin{cases*}
+ \hphantom{-}0 & falls $p~\vert~a$ \\[-1ex]
+ \hphantom{-}1 & falls $\exists x \in \mathbb{Z}\backslash p\mathbb{Z} : a \equiv x^2 \bmod p$ \\[-1ex]
+ -1 & sonst
+ \end{cases*} \\
+ \legendre{-1}{p} = (-1)^{\frac{p - 1}{2}} &=
+ \begin{cases*}
+ \hphantom{-}1 & falls $p \equiv 1 \bmod 4$ \\[-1ex]
+ -1 & falls $p \equiv 3 \bmod 4$
+ \end{cases*} \\
+ \legendre{2}{p} = (-1)^{\frac{p^2 - 1}{8}} &=
+ \begin{cases*}
+ \hphantom{-}1 & falls $p \equiv \pm 1 \bmod 8$ \\[-1ex]
+ -1 & falls $p \equiv \pm 3 \bmod 8$
+ \end{cases*}
+ \end{align*}
+ \begin{align*}
+ \legendre{p}{q} \cdot \legendre{q}{p} = (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} &&
+ \legendre{a}{p} \equiv a^{\frac{p-1}{2}}\bmod p
+ \end{align*}
+ \sourcecode{math/legendre.cpp}
+\end{algorithm}
+\optional{
\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
\begin{methods}
\method{init}{berechnet $\pi$ bis $N$}{N\*\log(\log(N))}
@@ -286,6 +314,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \method{pi}{zählt Primzahlen $\leq n$ ($n < N^2$)}{n^{2/3}}
\end{methods}
\sourcecode{math/piLehmer.cpp}
+}
\begin{algorithm}{Lineare Rekurrenz}
\begin{methods}
@@ -336,33 +365,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/matrixPower.cpp}
\end{algorithm}
-\begin{algorithm}{\textsc{Legendre}-Symbol}
- Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$:
- \begin{align*}
- \legendre{a}{p} &=
- \begin{cases*}
- \hphantom{-}0 & falls $p~\vert~a$ \\[-1ex]
- \hphantom{-}1 & falls $\exists x \in \mathbb{Z}\backslash p\mathbb{Z} : a \equiv x^2 \bmod p$ \\[-1ex]
- -1 & sonst
- \end{cases*} \\
- \legendre{-1}{p} = (-1)^{\frac{p - 1}{2}} &=
- \begin{cases*}
- \hphantom{-}1 & falls $p \equiv 1 \bmod 4$ \\[-1ex]
- -1 & falls $p \equiv 3 \bmod 4$
- \end{cases*} \\
- \legendre{2}{p} = (-1)^{\frac{p^2 - 1}{8}} &=
- \begin{cases*}
- \hphantom{-}1 & falls $p \equiv \pm 1 \bmod 8$ \\[-1ex]
- -1 & falls $p \equiv \pm 3 \bmod 8$
- \end{cases*}
- \end{align*}
- \begin{align*}
- \legendre{p}{q} \cdot \legendre{q}{p} = (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} &&
- \legendre{a}{p} \equiv a^{\frac{p-1}{2}}\bmod p
- \end{align*}
- \sourcecode{math/legendre.cpp}
-\end{algorithm}
-
\begin{algorithm}{Inversionszahl}
\sourcecode{math/inversions.cpp}
\end{algorithm}
@@ -417,14 +419,13 @@ so gilt \end{methods}
\sourcecode{math/binomial0.cpp}
Falls $n >= p$ for $\mathit{mod}=p^k$ berechne \textit{fac} und \textit{inv} aber teile $p$ aus $i$ und berechne die häufigkeit von $p$ in $n!$ als $\sum\limits_{i=1}\big\lfloor\frac{n}{p^i}\big\rfloor$
-\columnbreak
-
- \begin{methods}
+
+ \begin{methods}
\method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k}
\end{methods}
\sourcecode{math/binomial1.cpp}
-
- \begin{methods}
+
+ \begin{methods}
\method{calc\_binom}{berechnet Binomialkoeffizient modulo Primzahl $p$}{p-n}
\end{methods}
\sourcecode{math/binomial3.cpp}
diff --git a/math/multInv.cpp b/math/multInv.cpp index 87603f3..647dc2d 100644 --- a/math/multInv.cpp +++ b/math/multInv.cpp @@ -1,5 +1,4 @@ -ll multInv(ll n, ll p) { - ll x, y; - extendedEuclid(n, p, x, y); // Implementierung von oben. - return ((x % p) + p) % p; +ll multInv(ll x, ll m) { + auto [d, a, b] = extendedEuclid(x, m); // Implementierung von oben. + return ((a % m) + m) % m; } diff --git a/math/shortModInv.cpp b/math/shortModInv.cpp index d5eaf07..f696cce 100644 --- a/math/shortModInv.cpp +++ b/math/shortModInv.cpp @@ -1,3 +1,3 @@ -ll multInv(ll a, ll b){ // a^{-1} mod b - return 1 < a ? b - multInv(b % a, a) * b / a : 1; +ll multInv(ll x, ll m) { // x^{-1} mod m + return 1 < x ? m - multInv(m % x, x) * m / x : 1; } diff --git a/math/transforms/seriesOperations.cpp b/math/transforms/seriesOperations.cpp index 3851a1e..4743674 100644 --- a/math/transforms/seriesOperations.cpp +++ b/math/transforms/seriesOperations.cpp @@ -1,55 +1,56 @@ -vector<ll> poly_inv(vector<ll> a, int n){ +vector<ll> poly_inv(const vector<ll>& a, int n) { vector<ll> q = {powMod(a[0], mod-2, mod)}; - for(int len = 1; len < n; len *= 2){ + for (int len = 1; len < n; len *= 2){ vector<ll> a2 = a, q2 = q; a2.resize(2*len), q2.resize(2*len); ntt(q2); - for(int j = 0; j < 2; j++){ + for (int j : {0, 1}) { ntt(a2); - for(int i = 0; i < 2*len; i++) a2[i] = a2[i] * q2[i] % mod; + for (int i = 0; i < 2*len; i++) a2[i] = a2[i]*q2[i] % mod; ntt(a2, true); - for(int i = 0; i < len; i++) a2[i] = 0; + for (int i = 0; i < len; i++) a2[i] = 0; } - for(int i = len; i < min(n, 2*len); i++) q.push_back((mod - a2[i]) % mod); - } + for (int i = len; i < min(n, 2*len); i++) { + q.push_back((mod - a2[i]) % mod); + }} return q; } -vector<ll> poly_deriv(vector<ll> a){ - for(int i = 0; i < sz(a)-1; i++) - a[i] = a[i+1] * (i+1) % mod; +vector<ll> poly_deriv(vector<ll> a) { + for (int i = 1; i < sz(a); i++) + a[i-1] = a[i] * i % mod; a.pop_back(); return a; } -vector<ll> poly_integr(vector<ll> a){ - if(a.empty()) return {0}; +vector<ll> poly_integr(vector<ll> a) { + if (a.empty()) return {0}; a.push_back(a.back() * powMod(sz(a), mod-2, mod) % mod); - for(int i = sz(a)-2; i > 0; i--) + for (int i = sz(a)-2; i > 0; i--) a[i] = a[i-1] * powMod(i, mod-2, mod) % mod; a[0] = 0; return a; } -vector<ll> poly_log(vector<ll> a, int n){ +vector<ll> poly_log(vector<ll> a, int n) { a = mul(poly_deriv(a), poly_inv(a, n)); a.resize(n-1); a = poly_integr(a); return a; } -vector<ll> poly_exp(vector<ll> a, int n){ +vector<ll> poly_exp(vector<ll> a, int n) { vector<ll> q = {1}; - for(int len = 1; len < n; len *= 2){ + for (int len = 1; len < n; len *= 2) { vector<ll> p = poly_log(q, 2*len); - for(int i = 0; i < 2*len; i++) + for (int i = 0; i < 2*len; i++) p[i] = (mod - p[i] + (i < sz(a) ? a[i] : 0)) % mod; vector<ll> q2 = q; q2.resize(2*len); ntt(p), ntt(q2); - for(int i = 0; i < 2*len; i++) p[i] = p[i] * q2[i] % mod; + for (int i = 0; i < 2*len; i++) p[i] = p[i] * q2[i] % mod; ntt(p, true); - for(int i = len; i < min(n, 2*len); i++) q.push_back(p[i]); + for (int i = len; i < min(n, 2*len); i++) q.push_back(p[i]); } return q; -}
\ No newline at end of file +} |