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.↵
↵
```cpp↵
#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](https://atcoder.jp/contests/practice2/tasks/practice2_c) ↵
↵
[EX — Popcount Sum(Atcoder)](https://atcoder.jp/contests/abc283/tasks/abc283_h)↵
↵
[G — Redistribution of Piles(Atcoder)](https://atcoder.jp/contests/abc313/tasks/abc313_g)↵
↵
[G — Ax + By < C(Atcoder)](https://atcoder.jp/contests/abc372/tasks/abc372_g)↵
↵
[Sum(UOJ)](https://uoj.ac/problem/42)↵
↵
[COCI2009-2010#1 ALADIN](https://hsin.hr/coci/archive/2009_2010/contest1_tasks.pdf)↵
↵
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](https://asfjwd.github.io/2020-04-24-floor-sum-ap/)↵
↵
---↵
↵
**Update1**: Add some problems in the list.↵
↵
**Update2**: Add a practice problem, fix some errors, thanks for contribution of [A\_Le\_K](/profile/A_Le_K "Master A_Le_K").↵
↵
**Update3**: Add an article of extension of sloor sum.
↵
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.↵
↵
```cpp↵
#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](https://atcoder.jp/contests/practice2/tasks/practice2_c) ↵
↵
[EX — Popcount Sum(Atcoder)](https://atcoder.jp/contests/abc283/tasks/abc283_h)↵
↵
[G — Redistribution of Piles(Atcoder)](https://atcoder.jp/contests/abc313/tasks/abc313_g)↵
↵
[G — Ax + By < C(Atcoder)](https://atcoder.jp/contests/abc372/tasks/abc372_g)↵
↵
[Sum(UOJ)](https://uoj.ac/problem/42)↵
↵
[COCI2009-2010#1 ALADIN](https://hsin.hr/coci/archive/2009_2010/contest1_tasks.pdf)↵
↵
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](https://asfjwd.github.io/2020-04-24-floor-sum-ap/)↵
↵
---↵
↵
**Update1**: Add some problems in the list.↵
↵
**Update2**: Add a practice problem, fix some errors, thanks for contribution of [A\_Le\_K](/profile/A_Le_K "Master A_Le_K").↵
↵
**Update3**: Add an article of extension of sloor sum.
