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/minMod.cpp | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+) create mode 100644 content/math/minMod.cpp (limited to 'content/math/minMod.cpp') 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 -- cgit v1.2.3