From 6ae1d00fca78145c73f826c5490452726b9bf161 Mon Sep 17 00:00:00 2001 From: Lucas Schwebler Date: Sat, 7 Sep 2024 22:02:34 +0200 Subject: add divSum (sum of floor linear) --- content/math/divSum.cpp | 9 +++++++++ 1 file changed, 9 insertions(+) create mode 100644 content/math/divSum.cpp (limited to 'content/math/divSum.cpp') diff --git a/content/math/divSum.cpp b/content/math/divSum.cpp new file mode 100644 index 0000000..dc4bc4d --- /dev/null +++ b/content/math/divSum.cpp @@ -0,0 +1,9 @@ +// Calculates the sum of (a*i+b)/m for i=0..(n-1) in O(log(n)) +// Note that b should not be negative! +ll divSum(ll n, ll m, ll a, ll b){ + if(m == 0) return 0; + ll ans = a/m * n*(n-1) / 2 + b/m * n; + a %= m, b %= m; + ll y = (a*(n-1)+b)/m; + return ans + y*(n-1) - divSum(y, a, m, m-b-1); +} \ No newline at end of file -- cgit v1.2.3