How to calculate floor sum?

#	User	Rating
1	tourist	3892
2	jiangly	3797
3	orzdevinwang	3706
4	jqdai0815	3682
5	ksun48	3588
6	ecnerwala	3557
7	Ormlis	3532
8	Benq	3468
9	Radewoosh	3463
10	Um_nik	3450

#	User	Contrib.
1	cry	164
2	Qingyu	159
3	-is-this-fft-	158
3	atcoder_official	158
5	Dominater069	155
6	adamant	154
7	djm03178	151
8	luogu_official	150
9	awoo	148
10	maomao90	145

The floor sum is an algorithm that solves for the value of a function approximating $$$f(a,b,c,n)=\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor$$$ in $$$O(\log n)$$$ time complexity.

Maybe you haven't heard of it, but you can get the algorithm by simple mathematical derivation.

Notice: If you want to master it, you'd better derive it on your own after reading the editorial.(prepare a draft paper)

To calculate the sum of the functions, $$$n \le 10^{9}$$$.

$$$f(a,b,c,n)=\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor$$$ $$$g(a,b,c,n)=\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor^2$$$ $$$h(a,b,c,n)=\sum\limits_{i=0}^ni\left\lfloor\frac{ai+b}{c}\right\rfloor$$$

(I) when $$$a < c$$$ and $$$b < c$$$.

First simplify $$$f(a,b,c,n)$$$.

$$$\begin{aligned} f(a,b,c,n)&=\sum_{i=0}^n\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\\&=\sum_{i=0}^n\sum_{j=1}^{\lfloor\frac{ai+b}{c}\rfloor}\bigg[j\le\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\bigg]\\&=\sum_{i=0}^n\sum_{j=1}^{\lfloor\frac{an+b}{c}\rfloor}\bigg[j\le\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\bigg]\\&=\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\bigg[j+1\le\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\bigg]\\&=\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\bigg[cj+c\le{ai+b}\bigg]\\&=\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\bigg[cj+c-b\le{ai}\bigg]\\&=\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\bigg[cj+c-b - 1<{ai}\bigg]\\&=\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\bigg[\bigg\lfloor\frac{cj+c-b - 1}{a}\bigg\rfloor<i\bigg]\\&=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=0}^n\bigg[\bigg\lfloor\frac{cj+c-b - 1}{a}\bigg\rfloor<i\bigg]\\&=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=\lfloor\frac{cj+c-b - 1}{a}\rfloor+1}^n1\\&=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\bigg(n-\bigg\lfloor\frac{cj+c-b - 1}{a}\bigg\rfloor\bigg)\\&=n\bigg\lfloor\frac{an+b}{c}\bigg\rfloor-\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\bigg\lfloor\frac{cj+c-b - 1}{a}\bigg\rfloor\\&=n\bigg\lfloor\frac{an+b}{c}\bigg\rfloor-f(c,c+b-1,a,\bigg\lfloor\frac{an+b}{c}\bigg\rfloor-1)\end{aligned}$$$

Let $$$m = \left\lfloor\frac{an+b}{c}\right\rfloor$$$, then we get:

$$$f(a,b,c,n) = nm-f(c,c-b-1,a,m-1)$$$

For the above derivation, we call it Lemma 1:

Lemma 1: $$$\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor=\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\sum\limits_{i=\left\lfloor\frac{cj+c-b - 1}{a}\right\rfloor+1}^n1$$$

Next consider the simplification of $$$h(a,b,c,n)$$$, which follows from Lemma 1:

$$$\begin{aligned} h(a,b,c,n)&=\sum_{i=0}^ni\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\\ &=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=\lfloor\frac{cj+c-b - 1}{a}\rfloor+1}^ni \end{aligned}$$$

Let $$$t = \left\lfloor\frac{cj+c-b-1}{a}\right\rfloor, m = \left\lfloor\frac{an+b}{c}\right\rfloor$$$, then:

$$$\begin{aligned} h(a,b,c,n)&= \sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=\lfloor\frac{cj+c-b-1}{a}\rfloor+1}^ni\\ &=\sum_{j=0}^{m-1}\sum_{i=t+1}^ni\\ &=\sum_{j=0}^{m-1}\frac{(t+n+1)(n-t)}{2} \end{aligned}$$$

Lemma 2: Let $$$t = \left\lfloor\frac{cj+c-b-1}{a}\right\rfloor, m = \left\lfloor\frac{an+b}{c}\right\rfloor$$$, then：

$$$\sum\limits_{i=0}^ni\left\lfloor\frac{ai+b}{c}\right\rfloor = \sum\limits_{j=0}^{m-1}\frac{(t+n+1)(n-t)}{2}$$$

Since $$$j$$$ in the expression for $$$t$$$ is related to summation, we present $$$t$$$ separately.

$$$\begin{aligned} \frac{(t+n)(n-t+1)}{2}&=\frac{1}{2}(n^2-t^2-t+n)\\ &=\frac{1}{2}((n^2+n)-(t^2+t)) \end{aligned}$$$

The original equation can then be simplified.

$$$\begin{aligned} \sum_{j=0}^{m-1}\frac{(t+n+1)(n-t)}{2}&=\sum_{j=0}^{m-1}\frac{1}{2}\bigg((n^2+n)-(t^2+t)\bigg)\\ &=\frac{1}{2}\sum_{j=0}^{m-1}\bigg(n^2+n\bigg)- \frac{1}{2}\sum_{j=0}^{m-1}\bigg(t^2+t\bigg)\\ &=\frac{mn^2+mn}{2}-\frac{1}{2}\sum_{j=0}^{m-1}t^2-\frac{1}{2}\sum_{j=0}^{m-1}t\\ &=\frac{1}{2}\bigg(mn^2+mn-\sum_{j=0}^{m-1}\bigg\lfloor\frac{cj+c-b-1}{a}\bigg\rfloor^2-\sum_{j=0}^{m-1}\bigg\lfloor\frac{cj+c-b-1}{a}\bigg\rfloor\bigg)\\ &=\frac{1}{2}\bigg(mn(n+1)-g(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1)\bigg) \end{aligned}$$$

Then consider the simplification of $$$g(a,b,c,n)$$$, where we know summation formula $$$\sum\limits_{i=1}^n i = \frac{n^2+n}{2}$$$, which can be inverted to get $$$2\sum\limits_{i=1}^n i - n = n^2$$$, whereupon our $$$g(a,b,c,n)$$$ can be turned into:

$$$\begin{aligned} g(a,b,c,n)&=\sum_{i=0}^n\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor^2\\ &=\sum_{i=0}^n\bigg(2\sum_{j=1}^{\lfloor\frac{ai+b}{c}\rfloor}j-\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\bigg)\\ &=\sum_{i=0}^n\bigg(2\sum_{j=1}^{\lfloor\frac{ai+b}{c}\rfloor}j - f(a,b,c,n)\bigg) \end{aligned}$$$

According to Lemma 2 it follows that for $$$t = \left\lfloor\frac{cj+c-b-1}{a}\right\rfloor, m = \left\lfloor\frac{an+b}{c}\right\rfloor$$$ and there are:

$$$\begin{aligned} g(a,b,c,n)&=\sum_{i=0}^n\bigg(2\sum_{j=1}^{\lfloor\frac{ai+b}{c}\rfloor}j - f(a,b,c,n)\bigg)\\ &=2\sum_{i=0}^n\sum_{j=1}^{\lfloor\frac{ai+b}{c}\rfloor}j-\sum_{i=0}^n\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\\ &=2\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{ai+b}{c}\rfloor-1}(j+1)-f(a,b,c,n)\\ &=2\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}(j+1)\bigg[j\le\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor-1\bigg]-f(a,b,c,n)\\ &=2\sum_{i=0}^n\sum_{j=0}^{m-1}(j+1)\bigg[j\le\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor-1\bigg]-f(a,b,c,n) \end{aligned}$$$

From Lemma 1:

$$$\begin{aligned} g(a,b,c,n)&=2\sum_{i=0}^n\sum_{j=0}^{m-1}(j+1)\bigg[\bigg\lfloor\frac{cj+c-b - 1}{a}\bigg\rfloor<i\bigg]-f(a,b,c,n)\\ &=2\sum_{j=0}^{m-1}(j+1)\bigg(n-\bigg\lfloor\frac{cj+c-b - 1}{a}\bigg\rfloor\bigg)-f(a,b,c,n)\\ &=2\sum_{j=0}^{m-1}(j+1)n-2\sum_{j=0}^{m-1}(j+1)\bigg\lfloor\frac{cj+c-b - 1}{a}\bigg\rfloor-f(a,b,c,n)\\ &=(m+1)mn-2\sum_{j=0}^{m-1}j\bigg\lfloor\frac{cj+c-b - 1}{a}\bigg\rfloor-2\sum_{j=0}^{m-1}\bigg\lfloor\frac{cj+c-b - 1}{a}\bigg\rfloor-f(a,b,c,n)\\ &=(m+1)mn-2\bigg(h(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1)\bigg)-f(a,b,c,n)\\ \end{aligned}$$$

From this, when $$$a \le c$$$ and $$$b \le c$$$, we have:

$$$\begin{aligned} &f(a,b,c,n) = nm-f(c,c-b-1,a,m-1)\\ &g(a,b,c,n) = (m+1)mn-2\bigg(h(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1)\bigg)-f(a,b,c,n)\\ &h(a,b,c,n) = \frac{1}{2}\bigg(mn(m+1)-g(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1)\bigg) \end{aligned}$$$

(II) When $$$a \ge c$$$ or $$$b \ge c$$$, we fully expand the equation so that $$$a'=a \bmod c$$$ and $$$b'=b \bmod c$$$.

$$$\begin{aligned} f(a,b,c,n) &= \sum_{i=0}^n\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\\ &=\sum_{i=0}^n\bigg(\bigg\lfloor\frac{a'i+b'}{c}\bigg\rfloor+i\bigg\lfloor\frac{a}{c}\bigg\rfloor+\bigg\lfloor\frac{b}{c}\bigg\rfloor\bigg)\\ &=f(a',b',c,n)+\frac{n(n+1)}{2}\bigg\lfloor\frac{a}{c}\bigg\rfloor+(n+1)\bigg\lfloor\frac{b}{c}\bigg\rfloor\\ g(a,b,c,n) &= \sum_{i=0}^n\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor^2\\ &=\sum_{i=0}^n\bigg(\bigg\lfloor\frac{a'i+b'}{c}\bigg\rfloor+i\bigg\lfloor\frac{a}{c}\bigg\rfloor+\bigg\lfloor\frac{b}{c}\bigg\rfloor\bigg)^2\\ &=\sum_{i=0}^n\bigg(\bigg\lfloor\frac{a'i+b'}{c}\bigg\rfloor^2+i^2\bigg\lfloor\frac{a}{c}\bigg\rfloor^2+\bigg\lfloor\frac{b}{c}\bigg\rfloor^2+2i\bigg\lfloor\frac{a'i+b'}{c}\bigg\rfloor+2i\bigg\lfloor\frac{a}{c}\bigg\rfloor\bigg\lfloor\frac{b}{c}\bigg\rfloor+2\bigg\lfloor\frac{b}{c}\bigg\rfloor\bigg\lfloor\frac{a'i+b'}{c}\bigg\rfloor\bigg)\\ &=g(a',b',c,n)+\frac{n(n+1)(2n+1)}{6}\bigg\lfloor\frac{a}{c}\bigg\rfloor^2+(n+1)\bigg\lfloor\frac{b}{c}\bigg\rfloor^2 \\ & ~ ~ ~ ~ ~+2\bigg(h(a',b',c,n)+\bigg\lfloor\frac{b}{c}\bigg\rfloor f(a',b',c,n)+\frac{n(n+1)}{2}\bigg\lfloor\frac{a}{c}\bigg\rfloor\bigg\lfloor\frac{b}{c}\bigg\rfloor\bigg)\\ h(a,b,c,n)&=\sum_{i=0}^ni\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\\ &=\sum_{i=0}^ni\bigg(\bigg\lfloor\frac{a'i+b'}{c}\bigg\rfloor+i\bigg\lfloor\frac{a}{c}\bigg\rfloor+\bigg\lfloor\frac{b}{c}\bigg\rfloor\bigg)\\ &=\sum_{i=0}^n h(a',b',c,n)+\frac{n(n+1)(2n+1)}{6}\bigg\lfloor\frac{a}{c}\bigg\rfloor+\frac{n(n+1)}{2}\bigg\lfloor\frac{b}{c}\bigg\rfloor \end{aligned}$$$

Write the code according to the formula, in order to prevent the data that has already been counted from being double counted, we use struct to store the three functions to calculate synchronously.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353, inv2 = 499122177, inv6 = 166374059;
int T;
ll a, b, c, n;
struct Node
{
    ll f, g, h;
};

Node solve(ll a, ll b, ll c, ll n)
{
    Node ans, tmp;
    if (!a) return (Node){(b / c) * (n + 1) % mod, (b / c) * (b / c) % mod * (n + 1) % mod, (b / c) * n % mod * (n + 1) % mod * inv2 % mod};
    if (a < c && b < c)
    {
        ll m = (a * n + b) / c;
        if (!m) return (Node){0, 0, 0};
        tmp = solve(c, c - b - 1, a, m - 1);
        m %= mod;
        ans.f = (m * n % mod - tmp.f + mod) % mod;
        ans.g = ((m * (m + 1) % mod * n % mod - 2 * tmp.h - 2 * tmp.f - ans.f) % mod + mod) % mod;
        ans.h = ((m * n % mod * (n + 1) % mod - tmp.f - tmp.g) % mod + mod) % mod * inv2 % mod;
        return ans;
    }
    tmp = solve(a % c, b % c, c, n);
    ans.f = (tmp.f + n * (n + 1) % mod * inv2 % mod * (a / c) % mod + (n + 1) * (b / c) % mod) % mod;
    ans.g = (tmp.g + (a / c) * (a / c) % mod * n % mod * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod + (n + 1) * (b / c) % mod * (b / c) % mod + 2 * (a / c) % mod * tmp.h % mod + 2 * (b / c) * tmp.f % mod + 2 * (a / c) * (b / c) % mod * n % mod * (n + 1) % mod * inv2 % mod) % mod;
    ans.h = (tmp.h + (a / c) * n % mod * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod + (b / c) * n % mod * (n + 1) % mod * inv2 % mod) % mod;
    return ans;
}

void solve()
{
    scanf("%lld%lld%lld%lld", &n, &a, &b, &c);
    Node ans = solve(a, b, c, n);
    printf("%lld %lld %lld\n", ans.f, ans.g, ans.h);
}

int main()
{
    scanf("%d", &T);
    while (T -- ) solve();
    return 0;
}

Then you may want to try some problems. Here are a list of ques I met before, hope you can solve them:)

Floor Sum(Atcoder) Practice this problem

EX — Popcount Sum(Atcoder)

G — Redistribution of Piles(Atcoder)

G — Ax + By < C(Atcoder)

Sum(UOJ)

COCI2009-2010#1 ALADIN

In fact, some higher dimensional cases can be obtained by similar derivations, I'd recommend you to watch this article for further study:

more extensions of floor sum

Update1: Add some problems in the list.

Update2: Add a practice problem, fix some errors, thanks for contribution of A_Le_K.

Update3: Add an article of extension of sloor sum.