summaryrefslogtreecommitdiff
path: root/content/math/minMod.cpp
diff options
context:
space:
mode:
authormzuenni <michi.zuendorf@gmail.com>2024-09-08 22:16:36 +0200
committermzuenni <michi.zuendorf@gmail.com>2024-09-08 22:16:36 +0200
commit45d95c45013bf4ff73570c94c58b7f0212ccdf26 (patch)
treee47f9b16f44acef5f2517655fe2a16f8108f5af1 /content/math/minMod.cpp
parentdf963645ca0c5d0bed4fb9c02e93233dcfd53dae (diff)
moved stuff
Diffstat (limited to 'content/math/minMod.cpp')
-rw-r--r--content/math/minMod.cpp26
1 files changed, 15 insertions, 11 deletions
diff --git a/content/math/minMod.cpp b/content/math/minMod.cpp
index 2db060a..91f31d0 100644
--- a/content/math/minMod.cpp
+++ b/content/math/minMod.cpp
@@ -1,18 +1,22 @@
-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);
+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 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;
+ ll l = ai*b % m;
+ ll 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