diff options
| author | mzuenni <michi.zuendorf@gmail.com> | 2024-09-08 22:16:36 +0200 |
|---|---|---|
| committer | mzuenni <michi.zuendorf@gmail.com> | 2024-09-08 22:16:36 +0200 |
| commit | 45d95c45013bf4ff73570c94c58b7f0212ccdf26 (patch) | |
| tree | e47f9b16f44acef5f2517655fe2a16f8108f5af1 /content/math/minMod.cpp | |
| parent | df963645ca0c5d0bed4fb9c02e93233dcfd53dae (diff) | |
moved stuff
Diffstat (limited to 'content/math/minMod.cpp')
| -rw-r--r-- | content/math/minMod.cpp | 26 |
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 |
