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}$$$.

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

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

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

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:

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

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

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

The original equation can then be simplified.

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:

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:

From Lemma 1:

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

(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$$$.

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:)

G — Ax + By < C(Atcoder)

Sum(UOJ)

EX — Popcount Sum(Atcoder)

[COCI2009-2010#1] ALADIN