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.↵
↵
### To calculate the sum of the functions, $n \le 10^{9}$.↵
↵
$$f(a,b,c,n)=\sum_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor$$↵
↵
$$g(a,b,c,n)=\sum_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor^2$$↵
↵
$$h(a,b,c,n)=\sum_{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:)↵
↵
[G — Ax + By < C(Atcoder)](https://atcoder.jp/contests/abc372/tasks/abc372_g)↵
↵
[Sum(UOJ)](https://uoj.ac/problem/42G — Redistribution of Piles](https://atcoder.jp/contests/abc313/tasks/abc313_g)↵
↵
[EX — Popcount Sum(Atcoder)](https://atcoder.jp/contests/abc283/tasks/abc283_h)↵
↵
[COCI2009-2010#1] ALADINSum(UOJ)](https://uoj.ac/problem/42)↵
↵
[COCI2009-2010#1] ALADIN↵
↵
**Update1**: Add some problems in the list.
↵
Maybe you haven't heard of it, but you can get the algorithm by simple mathematical derivation.↵
↵
### To calculate the sum of the functions, $n \le 10^{9}$.↵
↵
$$f(a,b,c,n)=\sum_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor$$↵
↵
$$g(a,b,c,n)=\sum_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor^2$$↵
↵
$$h(a,b,c,n)=\sum_{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:)↵
↵
[G — Ax + By < C(Atcoder)](https://atcoder.jp/contests/abc372/tasks/abc372_g)↵
↵
[
↵
[EX — Popcount Sum(Atcoder)](https://atcoder.jp/contests/abc283/tasks/abc283_h)↵
↵
[
↵
[COCI2009-2010#1] ALADIN↵
↵
**Update1**: Add some problems in the list.
