From 9e9c033aa41f786f494cadea43563f83f3e951a3 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 7 Sep 2024 23:41:49 +0200 Subject: insert divsum --- content/math/divSum.cpp | 15 +++++++-------- 1 file changed, 7 insertions(+), 8 deletions(-) (limited to 'content/math/divSum.cpp') diff --git a/content/math/divSum.cpp b/content/math/divSum.cpp index dc4bc4d..48302b5 100644 --- a/content/math/divSum.cpp +++ b/content/math/divSum.cpp @@ -1,9 +1,8 @@ -// 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 + 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); +} -- cgit v1.2.3