summaryrefslogtreecommitdiff
path: root/content/math/minMod.cpp
diff options
context:
space:
mode:
authormzuenni <michi.zuendorf@gmail.com>2024-09-08 23:21:15 +0200
committermzuenni <michi.zuendorf@gmail.com>2024-09-08 23:21:15 +0200
commitfb5d046c4e4ab2bec7b0642626e11cff5680f63f (patch)
treeba2455ddb122ed8e208ed5cd83fddc3a439154f9 /content/math/minMod.cpp
parent45d95c45013bf4ff73570c94c58b7f0212ccdf26 (diff)
fix minMod
Diffstat (limited to 'content/math/minMod.cpp')
-rw-r--r--content/math/minMod.cpp6
1 files changed, 3 insertions, 3 deletions
diff --git a/content/math/minMod.cpp b/content/math/minMod.cpp
index 91f31d0..a80e783 100644
--- a/content/math/minMod.cpp
+++ b/content/math/minMod.cpp
@@ -4,19 +4,19 @@ ll firstVal(ll a, ll m, ll l, ll r) {
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;
+ return v < 0 ? -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;
+ ll c = b % g;
m /= g;
a /= g;
b /= g;
ll ai = multInv(a, m);
ll l = ai*b % m;
ll r = (n-1 + ai*b) % m;
- if(n >= m || l > r) return c;
+ if (n >= m || l > r) return c;
return a * firstVal(ai, m, l, r) % m * g + c;
} \ No newline at end of file