From df963645ca0c5d0bed4fb9c02e93233dcfd53dae Mon Sep 17 00:00:00 2001 From: Lucas Schwebler 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 ++++++++++ tcr.pdf | Bin 691497 -> 693864 bytes test/math/minMod.cpp | 92 ++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 118 insertions(+), 1 deletion(-) create mode 100644 content/math/minMod.cpp create mode 100644 test/math/minMod.cpp 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 diff --git a/tcr.pdf b/tcr.pdf index c16c3cc..7dc830e 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/math/minMod.cpp b/test/math/minMod.cpp new file mode 100644 index 0000000..e49da11 --- /dev/null +++ b/test/math/minMod.cpp @@ -0,0 +1,92 @@ +#include "../util.h" +#include +#include + +ll naiveMinMod(ll n, ll m, ll a, ll b){ + ll ans = m; + for(ll i = 0; i < n; i++){ + ans = min(ans, (a*i+b)%m); + } + return ans; +} + +ll naiveFirstVal(ll a, ll m, ll l, ll r){ + for(ll i = 0; i < m; i++){ + ll v = a*i % m; + if(l <= v && v <= r) return v; + } + return -1; +} + +void stress_test_minMod() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = Random::integer(1, 100); + int m = Random::integer(1, 100); + int a = Random::integer(0, m); + int b = Random::integer(0, m); + ll expected = naiveMinMod(n, m, a, b); + ll got = minMod(n, m, a, b); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested queries: " << queries << endl; +} + +void stress_test_firstVal() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int m = Random::integer(1, 100); + int a = Random::integer(0, m); + int l = Random::integer(0, m); + int r = Random::integer(0, m); + if(l > r) swap(l, r); + ll expected = naiveFirstVal(a, m, l, r); + ll got = firstVal(a, m, l, r); + if (got != expected) cerr << a << " " << m << " " << l << " " << r << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test_minMod() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll n = Random::integer(1, 1'000'000'000); + ll m = Random::integer(1, 1'000'000'000); + ll a = Random::integer(0, m); + ll b = Random::integer(0, m); + t.start(); + hash += minMod(n, m, a, b); + t.stop(); + } + if (t.time > 750) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +void performance_test_firstVal() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll m = Random::integer(1, 1'000'000'000); + ll a = Random::integer(1, m); + ll l = Random::integer(0, m); + ll r = Random::integer(0, m); + if(l > r) swap(l, r); + t.start(); + hash += firstVal(a, m, l, r); + t.stop(); + } + if (t.time > 750) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test_minMod(); + stress_test_firstVal(); + performance_test_minMod(); + performance_test_firstVal(); +} + -- cgit v1.2.3