merge mzuenni changes

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
+}