From 9e9c033aa41f786f494cadea43563f83f3e951a3 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Sat, 7 Sep 2024 23:41:49 +0200
Subject: insert divsum

---
 content/math/divSum.cpp | 15 +++++++--------
 content/math/gauss.cpp  | 12 +++++-------
 content/math/lgsFp.cpp  |  3 +--
 content/math/math.tex   | 14 ++++++++++----
 4 files changed, 23 insertions(+), 21 deletions(-)

(limited to 'content/math')

diff --git a/content/math/divSum.cpp b/content/math/divSum.cpp
index dc4bc4d..48302b5 100644
--- a/content/math/divSum.cpp
+++ b/content/math/divSum.cpp
@@ -1,9 +1,8 @@
-// Calculates the sum of (a*i+b)/m for i=0..(n-1) in O(log(n))
-// Note that b should not be negative!
 ll divSum(ll n, ll m, ll a, ll b){
-	if(m == 0) return 0;
-	ll ans = a/m * n*(n-1) / 2 + b/m * n;
-	a %= m, b %= m;
-	ll y = (a*(n-1)+b)/m;
-	return ans + y*(n-1) - divSum(y, a, m, m-b-1);
-}
\ No newline at end of file
+	if (m == 0) return 0;
+	ll ans = a/m * n*(n-1)/2 + b/m * n;
+	a %= m;
+	b %= m;
+	ll y = (a*(n-1)+b) / m;
+	return ans + y * (n-1) - divSum(y, a, m, m-b-1);
+}
diff --git a/content/math/gauss.cpp b/content/math/gauss.cpp
index 8129fd2..d431e52 100644
--- a/content/math/gauss.cpp
+++ b/content/math/gauss.cpp
@@ -14,19 +14,17 @@ void takeAll(int n, int line) {
 int gauss(int n) {
 	vector<bool> done(n, false);
 	for (int i = 0; i < n; i++) {
-		int swappee = i; // Sucht Pivotzeile für bessere Stabilität.
-		for (int j = 0; j < n; j++) {
-			if (done[j]) continue;
-			if (abs(mat[j][i]) > abs(mat[i][i])) swappee = j;
+		int j = i; // Sucht Pivotzeile für bessere Stabilität.
+		for (int k = 0; k < n; k++) {
+			if (!done[k] && abs(mat[k][i]) > abs(mat[i][i])) j = k;
 		}
-		swap(mat[i], mat[swappee]);
+		swap(mat[i], mat[j]);
 		if (abs(mat[i][i]) > EPS) {
 			normalLine(i);
 			takeAll(n, i);
 			done[i] = true;	
 	}}
-	// Ab jetzt nur checks bzgl. Eindeutigkeit/Existenz der Lösung.
-	for (int i = 0; i < n; i++) {
+	for (int i = 0; i < n; i++) { // gauss fertig, prüfe Lösung
 		bool allZero = true;
 		for (int j = i; j < n; j++) allZero &= abs(mat[i][j]) <= EPS;
 		if (allZero && abs(mat[i][n]) > EPS) return INCONSISTENT;
diff --git a/content/math/lgsFp.cpp b/content/math/lgsFp.cpp
index 0241742..bf18c86 100644
--- a/content/math/lgsFp.cpp
+++ b/content/math/lgsFp.cpp
@@ -22,5 +22,4 @@ void gauss(int n, ll mod) {
 		normalLine(i, mod);
 		takeAll(n, i, mod);
 		done[i] = true;
-}}
-// für Eindeutigkeit, Existenz etc. siehe LGS über R @\sourceref{math/gauss.cpp}@
+}} // für Eindeutigkeit, Existenz etc. siehe LGS über R @\sourceref{math/gauss.cpp}@
diff --git a/content/math/math.tex b/content/math/math.tex
index c15825f..fffdf37 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -306,7 +306,10 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 \method{gauss}{löst LGS}{n^3}
 \sourcecode{math/gauss.cpp}
 
-\vfill\null\columnbreak
+\begin{algorithm}{Inversionszahl}
+	\vspace{-2pt}
+	\sourcecode{math/inversions.cpp}
+\end{algorithm}
 
 \begin{algorithm}{Numerisch Extremstelle bestimmen}
 	\sourcecode{math/goldenSectionSearch.cpp}
@@ -316,7 +319,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/simpson.cpp}
 \end{algorithm}
 
-
 \begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}
 	Multipliziert Polynome $A$ und $B$.
 	\begin{itemize}
@@ -340,8 +342,11 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
     \sourcecode{math/transforms/seriesOperations.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Inversionszahl}
-	\sourcecode{math/inversions.cpp}
+
+\begin{algorithm}{Div Sum}
+	\method{divSum}{berechnet $\sum_{i=0}^{n-1} \frac{a\cdot i + b}{m}$}{\log(n)}
+	\textbf{Wichtig:} $b$ darf nicht negativ sein!
+	\sourcecode{math/divSum.cpp}
 \end{algorithm}
 
 \subsection{Satz von \textsc{Sprague-Grundy}}
@@ -394,6 +399,7 @@ 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}
 		\method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k}
-- 
cgit v1.2.3