类欧几里得

真多啊麻麻地

Begin

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

先考虑 $a \geqslant c$ 或 $b \geqslant c$ 时的情况，直接把除拆开

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

发现左边是等差数列，右边是递归的形式

$$f(a,b,c,n) = \frac{n(n+1)}{2} \lfloor \frac{ai}c \rfloor + n\lfloor \frac bc \rfloor + f(a\%c,b\%c,c,n)$$

再来考虑 $a \lt c$ 和 $b < c$ 的情况，我们变一下

$$f(a,b,c,n) = \sum\limits_{i=0}^n \left \lfloor \frac{ai + b}{c}\right \rfloor = \sum\limits_{i=0}^n \sum\limits_{j=0}^{\left \lfloor \frac{ai + b}{c}\right \rfloor -1} 1$$

然后把 $j$ 移到 $i$ 前面去，令 $m = \left \lfloor \frac{an + b}{c}\right \rfloor$

$$=\sum\limits_{j=0}^{m -1} \sum\limits_{i=0}^n \left[j < \left \lfloor \frac{ai + b}{c}\right \rfloor \right]$$

尝试把条件变一变

\begin{align} [j < \left \lfloor \frac{ai + b}{c}\right \rfloor] &= [j+1 \leqslant \frac{ai + b}{c}] = [jc+c \leqslant ai+b] \nonumber\\ &= [ai \geqslant jc+c-b] = [ai \geqslant jc+c-b-1]\nonumber \end{align}

这样

\begin{align} f(a,b,c,n) &= \sum\limits_{j=0}^{m-1}\sum\limits_{i=0}^n \left[i >= \frac{jc+c-b-1}{a} \right] \nonumber\\ &= \sum\limits_{j=0}^{m-1} \left ( n-\frac{jc+c-b-1}{a} \right ) \nonumber\\ &= nm - f(c,c-b-1,a,m-1) \nonumber \end{align}

然后发现可求

可以发现我们递归的过程类似于辗转相除，因此这个算法叫做 ‘’类欧几里得‘’。

拓展

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

g

经典分情况

$a \geqslant c$ 或 $b \geqslant c$ 时

\begin{align} g(a,b,c,n) &= \sum\limits_{i = 0}^n \left \lfloor \frac{ai + b}{c}\right \rfloor i \nonumber\\ &= \sum\limits_{i = 0}^n \lfloor \frac{ai}c \rfloor i + \sum\limits_{i = 0}^n \lfloor \frac bc \rfloor i+ \sum\limits_{i = 0}^n \left \lfloor \frac{ai \% c + b\%c}{c}\right \rfloor i \nonumber\\ &= \lfloor \frac{a}{c} \rfloor \frac{n(n+1)(2n+1)}{6} + \lfloor \frac{b}{c} \rfloor \frac{n(n+1)}{2}\nonumber\\ &+ g(a\%c, b \% c, c, n)\nonumber \end{align}

$a \lt c$ 和 $b < c$ 时

令 $m = \lfloor \frac{an + b}{c} \rfloor$

\begin{align} g(a,b,c,n) &= \sum\limits_{j=0}^{m -1} \sum\limits_{i=0}^n \left[j < \left \lfloor \frac{ai + b}{c}\right \rfloor \right]i \nonumber\\ &=\sum\limits_{j=0}^{m -1} \sum\limits_{i=0}^n \left[i >= \frac{jc+c-b-1}{a} \right]i \nonumber \end{align}

令 $t = jc+b-c-1$

\begin{align} g(a,b,c,n) &= \sum\limits_{j=0}^{m-1} \frac{1}{2} (t+n+1)(n-t) \nonumber\\ &= \frac{1}{2} \left [ nm(m+1) - \sum_{j=0}^{m-1}t^2 - \sum_{j=0}^{m-1}t \right ] \nonumber\\ &= \frac{1}{2} \left [ mn(n+1) - h(c, c-b-1, a, m-1) - f(c, c-b-1, a, m-1) \right] \nonumber \end{align}

h

真 🐔 8️⃣ 🐴 🍚 ，不推了

注意 $n^2$ 换成 $2 \frac{n(n+1)}{2} - n$ 也就是 $\left( 2\sum\limits_{i=0}^{n} \right) - n$ 这样子就没有 $\sum \times \sum$ 了

$a \geqslant c$ 或 $b \geqslant c$ 时

\begin{align} h(a,b,c,n) &= h(a \% c, b \% c, c, n)\nonumber\\ &+ 2 \lfloor \frac{b}{c} \rfloor f(a \%c, b\%c,c,n) + 2 \lfloor \frac{b}{c} \rfloor g(a \%c, b\%c,c,n)\nonumber\\ &+ \lfloor \frac{a}{c} \rfloor^2 \frac{n(n+1)(2n+1)}{6} + \lfloor \frac{b}{c} \rfloor^2(n+1) + \lfloor \frac{a}{c} \rfloor\lfloor \frac{b}{c} \rfloor n(n+1)\nonumber \end{align}

$a \lt c$ 和 $b < c$ 时

\begin{align} h(a,b,c,n) &= nm(m+1) \nonumber\\ &- 2g(c, c-b-1, a, m-1) - 2f(c, c-b-1, a, m-1) - f(a, b, c, n)\nonumber \end{align}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t;
ll n,a,b,c;
const ll p = 998244353;
const ll inv2 = 499122177;
const ll inv6 = 166374059;
struct node
{
    ll f, g, h;
};
node work(ll a, ll b, ll c, ll n)
{
    ll ac = a/c, bc = b/c, m = (a*n+b)/c, n1 = n+1, n2 = n*2+1;
    node x;
    if(a == 0)
    {
        x.f = bc*n1%p;
        x.g = bc*n%p * n1%p * inv2%p;
        x.h = bc*bc%p * n1%p;
        return x;
    }
    if(a >= c || b >= c)
    {
        x.f = n*n1%p * inv2%p * ac%p + bc*n1%p;
        x.g = ac*n%p * n1%p * n2%p * inv6%p + bc * n%p * n1%p *inv2%p;
        x.h = ac*ac%p * n%p * n1%p * n2%p *inv6%p + 
              bc*bc%p * n1%p +
              ac*bc%p * n%p * n1%p;
        x.f %= p; x.g %= p; x.h %= p;

        node e = work(a%c, b%c, c, n);

        x.h = (x.h + e.h + 2 * bc%p * e.f%p + 2 * e.g%p * ac%p)%p;
        x.f = (x.f + e.f)%p;
        x.g = (x.g + e.g)%p;
        x.h %= p;
        return x;
    }
    node e = work(c, c-b-1, a, m-1);
    x.f = ((n * m%p - e.f)%p + p)%p;
    x.g = ((n * m%p * n1%p - e.h - e.f) * inv2%p +p) %p;
    x.h = ((n * m%p * (m+1)%p - 2*e.g - 2*e.f - x.f)%p + p)%p;
    return x;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
        node ans = work(a, b, c, n);
        printf("%lld %lld %lld\n",ans.f, ans.h, ans.g);
    }
    
    return 0;
}