diff options
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 |