Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

类欧几里得

Posted on

求解$\sum_{i=0}^n\left \lfloor \frac{ai+b}{c} \right \rfloor$之类的式子。

第一类

令$f(a,b,c,n)=\sum_{i=0}^n\left \lfloor \frac{ai+b}{c} \right \rfloor$

我们对此分类讨论：

1.$a\ge c \ or \ b \ge c$

考虑去掉向下取整：
$$
\begin{aligned}
f(a,b,c,n)&=\sum_{i=0}^n\left \lfloor \frac{ai+b}{c} \right \rfloor\\
&=\sum_{i=0}^n\left \lfloor \frac{(a\% c+ \left \lfloor \frac{a}{c} \right \rfloor c)i+b \% c+\left \lfloor \frac{b}{c} \right \rfloor c}{c} \right \rfloor\\
&=\left \lfloor \frac{a}{c} \right \rfloor \times\frac{n(n+1)}{2}+\left \lfloor \frac{b}{c} \right \rfloor \times (n+1) + \sum_{i=0}^n\left \lfloor \frac{a \% c \times i+ b \% c}{c} \right \rfloor
\end{aligned}
$$
2.$a<c \ and \ b < c$

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

则有：
$$
\begin{aligned}
f(a,b,c,n)&=\sum_{i=0}^n\sum_{j=1}^m[j \le \left \lfloor \frac{ai+b}{c} \right \rfloor]\\
&= \sum_{i=0}^n\sum_{j=0}^{m-1}[j +1\le \left \lfloor \frac{ai+b}{c} \right \rfloor]\\
&=\sum_{i=0}^n\sum_{j=0}^{m-1}[i \ge \left \lfloor \frac{jc+c-b}{a} \right \rfloor]\\
&=\sum_{i=0}^n\sum_{j=0}^{m-1}[i > \left \lfloor \frac{jc+c-b-1}{a} \right \rfloor]\\
&=\sum_{j=0}^{m-1}\sum_{i=0}^n[i > \left \lfloor \frac{jc+c-b-1}{a} \right \rfloor]\\
&=\sum_{j=0}^{m-1}\sum_{i=0}^n[i > \left \lfloor \frac{jc+c-b-1}{a} \right \rfloor]\\
&=\sum_{j=0}^{m-1}n- \left \lfloor \frac{jc+c-b-1}{a} \right \rfloor\\
&=nm - f(c, c-b-1,a,m-1)\\
\end{aligned}
$$
故：
$$
f(a,b,c,n)=nm-f(c,c-b-1,a,m-1)
$$
展开$m$：
$$
f(a,b,c,n)=n\left \lfloor \frac{an+b}{c} \right \rfloor -f(c,c-b-1,a,\left \lfloor \frac{an+b}{c} \right \rfloor-1)
$$
直接递归处理即可，递归边界显然应该是$a=0$。

则：

$$
f(a,b,c,n)=
\begin{cases}
& \left \lfloor \frac{a}{c} \right \rfloor \times\frac{n(n+1)}{2}+\left \lfloor \frac{b}{c} \right \rfloor \times (n+1) + f(a \% c,b \% c,c, n), \ a\ge c \ or \ b \ge c \\
& n\left \lfloor \frac{an+b}{c} \right \rfloor -f(c,c-b-1,a,\left \lfloor \frac{an+b}{c} \right \rfloor-1), \ a<c \ and \ b < c
\end{cases}
$$

第二类

令$g(a,b,c,n)=\sum_{i=0}^n i \left \lfloor \frac{ai+b}{c} \right \rfloor$

小结论

$$
\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}
$$

1.$a \ge c \ or b \ge c$

像$f$一样考虑：
$$
\begin{aligned}
g(a,b,c,n)&=\sum_{i=0}^ni\left \lfloor \frac{ai+b}{c} \right \rfloor\\
&=\sum_{i=0}^ni \left \lfloor \frac{(a\% c+ \left \lfloor \frac{a}{c} \right \rfloor c)i+b \% c+\left \lfloor \frac{b}{c} \right \rfloor c}{c} \right \rfloor\\
&=\left \lfloor \frac{a}{c} \right \rfloor \times\frac{n(n+1)(2n+1)}{6}+\left \lfloor \frac{b}{c} \right \rfloor \times \frac{n(n+1)}{2} + g(a \% c, b \% c, c, n)
\end{aligned}
$$
2.$a<c \ and \ b < c$

那么同样的，设：
$$
m=\left \lfloor \frac{an+b}{c} \right \rfloor
$$
同上可得：
$$
g(a,b,c,n)=\sum_{i=0}^ni\sum_{j=0}^{m-1}[i > \left \lfloor \frac{jc+c-b-1}{a} \right \rfloor]
$$
这里有一个等差数列（我愣是没能看出来）

则：
$$
\begin{aligned}
g(a,b,c,n) &=\sum_{j=0}^{m-1} \frac{(\left \lfloor \frac{jc+c-b-1}{a} \right \rfloor +1+n)(n-\left \lfloor \frac{jc+c-b-1}{a} \right \rfloor)}{2}\\
&= \left \lfloor \frac{mn(n+1)-f(c,c-b-1,a,m-1)-h(c,c-b-1,a,m-1)}{2} \right \rfloor
\end{aligned}
$$
即：
$$
g(a,b,c,n)= \left \lfloor \frac{\left \lfloor \frac{an+b}{c} \right \rfloor n(n+1)-f(c,c-b-1,a,\left \lfloor \frac{an+b}{c} \right \rfloor - 1)-h(c,c-b-1,a,\left \lfloor \frac{an+b}{c} \right \rfloor-1)}{2} \right \rfloor
$$
则：

$$
g(a,b,c,n)=
\begin{cases}
& \left \lfloor \frac{a}{c} \right \rfloor \times\frac{n(n+1)(2n+1)}{6}+\left \lfloor \frac{b}{c} \right \rfloor \times \frac{n(n+1)}{2} + g(a \% c, b \% c, c, n), \ a\ge c \ or \ b \ge c \\
& \left \lfloor \frac{\left \lfloor \frac{an+b}{c} \right \rfloor n(n+1)-f(c,c-b-1,a,\left \lfloor \frac{an+b}{c} \right \rfloor - 1)-h(c,c-b-1,a,\left \lfloor \frac{an+b}{c} \right \rfloor-1)}{2} \right \rfloor, \ a<c \ and \ b < c \\
\end{cases}
$$

上面的$h$是不是很蒙，因为它是第三类。

第三类

令$h(a,b,c,n)=\sum_{i=0}^n \left \lfloor \frac{ai+b}{c} \right\rfloor^2$。

推导太恶心了，看着办吧。

$$
h(a,b,c,n) =
\begin{cases}
& h(a \% c, b \% c, c, n)+ 2\left \lfloor \frac{a}{c} \right \rfloor f(a \% c,b \% c,c, n) +\frac{n(n+1)(2n+1)}{6}\left \lfloor \frac{a}{c} \right \rfloor^2+n(n+1)\left \lfloor \frac{a}{c} \right \rfloor\left \lfloor \frac{b}{c} \right \rfloor, \ a\ge c \ or \ b \ge c \\
& n\left \lfloor \frac{an+b}{c} \right \rfloor(\left \lfloor \frac{an+b}{c} \right \rfloor+1)-2f(c,c-b-1,a,\left \lfloor \frac{an+b}{c} \right \rfloor-1)-2g(c,c-b-1,a,\left \lfloor \frac{an+b}{c} \right \rfloor-1)-f(a,b,c,n), \ a<c \ and \ b < c\\
\end{cases}
$$

Code

记忆化搜索

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') flag = 1; c = getchar(); }
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...ARC>
inline void read(T &res, ARC &...com){ read(res), read(com...); }
template <class T>
inline void out(T res)
{
    if(res < 0) putchar('-'), res = -res;
    if(res > 10) out(res / 10);
    putchar(res % 10 + '0'); 
}
template <class T>
inline void write(T res)
{
    out(res), putchar(' ');
}
const int mod = 998244353, inv2 = (mod + 1) >> 1, inv6 = 166374059, Mod = 1e9 + 7, bas = 43963;
int T;
int n, a, b, c;
unordered_map<LL, int>F, G, H;
int f(int a, int b, int c, int n);
int g(int a, int b, int c, int n);
int h(int a, int b, int c, int n);
inline LL Hash(int x, int y, int z, int n)
{
    return (((LL)x * bas % Mod + y) % Mod * bas + z) % Mod * bas + n;
}
int f(int a, int b, int c, int n)
{
    if(!a) return 1ll * b / c * (n + 1) % mod;
    LL res = Hash(a, b, c, n);
    if(F.find(res) != F.end()) return F[res];
    if(a >= c || b >= c) return F[res] = ((LL)a / c * n % mod * (n + 1) % mod * inv2 + 1ll * b / c * (n + 1) + f(a % c, b % c, c, n)) % mod;
    int m = ((LL)a * n + b) / c;
    return F[res] = (1ll * n * m - f(c, c - b - 1, a, m - 1) + mod) % mod;
}
inline int pw(int x)
{
    return 1ll * x * x % mod;
}
int h(int a, int b, int c, int n)
{
    if(!a) return 1ll * pw(b / c) * (n + 1) % mod;
    LL res = Hash(a, b, c, n);
    if(H.find(res) != H.end()) return H[res];
    if(a >= c || b >= c) return H[res] = (h(a % c, b % c, c, n) + 1ll * n * (n + 1) % mod * (2ll * n + 1) % mod * inv6 % mod * pw(a / c) + 1ll * (n + 1) * pw(b / c) + 1ll * n * (n + 1) % mod * (a / c) % mod * (b / c) + b / c * 2ll * f(a % c, b % c, c, n) + a / c * 2ll % mod * g(a % c, b % c, c, n)) % mod;
    int m = ((LL)a * n + b) / c;
    return H[res] = (1ll * m * n % mod * (m + 1) - f(a, b, c, n) - 2 * ((LL)g(c, c - b - 1, a, m - 1) + f(c, c - b - 1, a, m - 1)) + mod + mod + mod) % mod;
}
int g(int a, int b, int c, int n)
{
    if(!a) return (LL)b / c * n % mod * (n + 1) % mod * inv2 % mod;
    LL res = Hash(a, b, c, n); 
    if(G.find(res) != G.end()) return G[res];
    if(a >= c || b >= c) return G[res] = (g(a % c, b % c, c, n) + 1ll * n * (n + 1) % mod * (2ll * n + 1) % mod * inv6 % mod * (a / c) + 1ll * n * (n + 1) % mod * inv2 % mod * (b / c)) % mod;
    int m = ((LL)a * n + b) / c;
    return G[res] = (1ll * m * n % mod * (n + 1) - h(c, c - b - 1, a, m - 1) - f(c, c - b - 1,a, m - 1) + mod + mod) % mod * inv2 % mod;
}
mt19937 rnd(114514);
inline void work()
{
    read(n, a, b, c);
    printf("%d %d %d\n", (f(a, b, c, n) + mod) % mod, (h(a, b, c, n) + mod) % mod, (g(a, b, c, n) + mod) % mod);
    if(rnd() % 100 == 9) F.clear(), G.clear(), H.clear();
}
int main()
{
    read(T);
    while(T --) work();
    return 0;
}

同步计算（faster）

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') flag = 1; c = getchar(); }
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...ARC>
inline void read(T &res, ARC &...com){ read(res), read(com...); }
template <class T>
inline void out(T res)
{
    if(res > 9) out(res / 10);
    putchar(res % 10 + '0'); 
}
template <class T>
inline void write(T res)
{
    if(res < 0) putchar('-'), res = -res;
    out(res);
}
template <>
inline void write(char c){ putchar(c); }
template <>
inline void write(const char *s) { while(*s) putchar(*s ++); }
template<class T, class ...ARC>
inline void write(T res, ARC ...com){ write(res), write(com...);}
const int mod = 998244353, inv2 = (mod + 1) >> 1, inv6 = 166374059, Mod = 1e9 + 7, bas = 43963;
int T;
int n, a, b, c;
struct Node{
    int f, h, g;
};
inline int pw(int x)
{
    return 1ll * x * x % mod;
}
Node get_ans(int a, int b, int c, int n)
{
    Node now;
    if(!a)
    {
        now.f = 1ll * b / c * (n + 1) % mod;
        now.h = 1ll * pw(b / c) * (n + 1) % mod;
        now.g = 1ll * b / c * n % mod * (n + 1) % mod * inv2 % mod;
        return now;
    }
    if(a >= c || b >= c)
    {
        Node last = get_ans(a % c, b % c, c, n);
        now.f = ((LL)a / c * n % mod * (n + 1) % mod * inv2 + 1ll * b / c * (n + 1) + last.f) % mod;
        now.h = (last.h + 1ll * n * (n + 1) % mod * (2ll * n + 1) % mod * inv6 % mod * pw(a / c) + (LL)(n + 1) * pw(b / c) + 1ll * n * (n + 1) % mod * (a / c) % mod * (b / c) + b / c * 2ll * last.f + a / c * 2ll % mod * last.g) % mod;
        now.g = (last.g + 1ll * n * (n + 1) % mod * (2ll * n + 1) % mod * inv6 % mod * (a / c) + 1ll * n * (n + 1) % mod * inv2 % mod * (b / c)) % mod;
        return now;
    }
    int m = (1ll * a * n + b) / c;
    Node last = get_ans(c, c - b - 1, a, m - 1);
    now.f = (1ll * n * m - last.f) % mod;
    now.h = (1ll * n * m % mod * (m + 1) - now.f + 2 * (2ll * mod - last.g - last.f) + mod) % mod;
    now.g = (1ll * n * m % mod * (n + 1) - last.h - last.f + 2ll * mod) % mod * inv2 % mod;
    return now;
}
inline void work()
{
    read(n, a, b, c);
    Node ans = get_ans(a, b, c, n);
    write(ans.f, ' ', ans.h, ' ', ans.g, '\n');
}
int main()
{
    read(T);
    while(T --) work();
    return 0;
}