From df963645ca0c5d0bed4fb9c02e93233dcfd53dae Mon Sep 17 00:00:00 2001
From: Lucas Schwebler <lucas.schwebler@gmail.com>
Date: Sun, 8 Sep 2024 14:57:14 +0200
Subject: add min mod (mimumum of linear function modulo m)

---
 content/math/math.tex   |  9 ++++++++-
 content/math/minMod.cpp | 18 ++++++++++++++++++
 2 files changed, 26 insertions(+), 1 deletion(-)
 create mode 100644 content/math/minMod.cpp

(limited to 'content')

diff --git a/content/math/math.tex b/content/math/math.tex
index fffdf37..6b765ca 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -344,11 +344,18 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 
 
 \begin{algorithm}{Div Sum}
-	\method{divSum}{berechnet $\sum_{i=0}^{n-1} \frac{a\cdot i + b}{m}$}{\log(n)}
+	\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}
+	\method{firstVal}{berechnet den ersten Wert von $0,\ a, \ldots,\ a \cdot i \bmod{m}$, der in $[l, r]$ liegt. Gibt $-1$ zurück, falls er nicht existiert.}{\log(m)}
+	\method{minMod}{berechnet das Minimum von $(a \cdot i + b) \bmod{m}$ für $i \in [0, n)$}{\log(m)}
+	\textbf{Wichtig:} $0 \leq a, b, l, r < m$
+	\sourcecode{math/minMod.cpp}
+\end{algorithm}
+
 \subsection{Satz von \textsc{Sprague-Grundy}}
 Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu:
 \[
diff --git a/content/math/minMod.cpp b/content/math/minMod.cpp
new file mode 100644
index 0000000..2db060a
--- /dev/null
+++ b/content/math/minMod.cpp
@@ -0,0 +1,18 @@
+ll firstVal(ll a, ll m, ll l, ll r){
+	if(l == 0) return 0;
+	if(a == 0) return -1;
+	if((l-1)/a < r/a) return (l+a-1)/a*a;
+	ll s = (r+a-1)/a*a;
+	ll v = firstVal(m%a, a, s-r, s-l);
+	return v == -1 ? -1 : s - v;
+}
+
+ll minMod(ll n, ll m, ll a, ll b){
+	if(a == 0) return b;
+	ll g = gcd(m, a), c = b%g;
+	m /= g, a /= g, b /= g;
+	ll ai = multInv(a, m);
+	ll l = ai*b % m, r = (n-1 + ai*b) % m;
+	if(n >= m || l > r) return c;
+	return a * firstVal(ai, m, l, r) % m * g + c;
+}
\ No newline at end of file
-- 
cgit v1.2.3