跳转至

类欧几里得算法

「类欧几里得算法」与「欧几里得算法」的共同之处—— 仅是均使用了「辗转相除」来证明复杂度。

简介

已知 \(a, b, c, n\),求 $$ \begin{aligned} f(a, b, c, n) & = \sum_{i = 0}^{n}\left\lfloor\dfrac{ai + b}{c}\right\rfloor \\ g(a, b, c, n) & = \sum_{i = 0}^{n}\left(i\cdot\left\lfloor\dfrac{ai + b}{c}\right\rfloor\right) \\ h(a, b, c, n) & = \sum_{i = 0}^{n}\left(\left\lfloor\dfrac{ai + b}{c}\right\rfloor\right)^2 \end{aligned} $$

\(t (1 \le t \le 10^5)\) 组数据,\(0 \le a, b, c, n \le 10^9\)\(c \neq 0\)

理论推导

推导之前

\(m = \left\lfloor\dfrac{an + b}{c}\right\rfloor, t = \left\lfloor\dfrac{cj + c - b - 1}{a}\right\rfloor\),下文的方括号均为 艾佛森括号

结论

在推式子之前,我们先要证明一个常用的结论。 $$ \begin{aligned} \sum_{j = 0}^{m - 1}\sum_{i = 0}^{n}\left[j < \left\lfloor\dfrac{ai + b}{c}\right\rfloor\right] = \sum_{j = 0}^{m - 1}\sum_{i = 0}^{n}\left[i > t\right] \end{aligned} $$

证明

注意到 $$ \begin{aligned} j < \left\lfloor\dfrac{ai + b}{c}\right\rfloor & \Leftrightarrow j + 1 \le \left\lfloor\dfrac{ai + b}{c}\right\rfloor \\ & \Leftrightarrow j + 1 \le \dfrac{ai + b}{c} \\ & \Leftrightarrow cj + c \le ai + b \\ & \Leftrightarrow cj + c - 1 < ai + b \\ & \Leftrightarrow cj - b + c - 1 < ai \\ & \Leftrightarrow i > \left\lfloor\dfrac{cj + c - b - 1}{a}\right\rfloor \\ & \Leftrightarrow i > t \end{aligned} $$

所以原命题得证。

f

首先我们来求 \(f(a, b, c, n)\) 的递推式。

我们 定义 \(f(a, b, c, n) = \sum_{i = 0}^{n}\left\lfloor\dfrac{ai + b}{c}\right\rfloor\)

  • \(a \ge c\)\(b \ge c\) 时: $$ \begin{aligned} f(a, b, c, n) & = \sum_{i = 0}^{n}\left\lfloor\dfrac{ai + b}{c}\right\rfloor \\ & = \sum_{i = 0}^{n}\left\lfloor\dfrac{\left(\left\lfloor\dfrac{a}{c}\right\rfloor\cdot c + a \bmod c\right) \cdot i + \left(\left\lfloor\dfrac{b}{c}\right\rfloor\cdot c + b \bmod c\right)}{c}\right\rfloor \\ & = \sum_{i = 0}^{n}\left(\left\lfloor\dfrac{a}{c}\right\rfloor\cdot i + \left\lfloor\dfrac{b}{c}\right\rfloor + \left\lfloor\dfrac{\left(a \bmod c\right) \cdot i + \left(b \bmod c\right)}{c}\right\rfloor\right) \\ & = \left(\sum_{i = 0}^{n}\left\lfloor\dfrac{\left(a \bmod c\right) \cdot i + \left(b \bmod c\right)}{c}\right\rfloor\right) + \left(\left\lfloor\dfrac{a}{c}\right\rfloor\cdot\sum_{i = 0}^{n}i\right) + \left(\left\lfloor\dfrac{b}{c}\right\rfloor\cdot\sum_{i = 0}^{n}1\right)\\ & = f(a \bmod c, b \bmod c, c, n) + \dfrac{n(n + 1)}{2}\cdot\left\lfloor\dfrac{a}{c}\right\rfloor + (n + 1)\cdot\left\lfloor\dfrac{b}{c}\right\rfloor \end{aligned} $$

  • \(a < c\)\(b < c\) 时: $$ \begin{aligned} f(a, b, c, n) & = \sum_{i = 0}^{n}\left\lfloor\dfrac{ai + b}{c}\right\rfloor \\ & = \sum_{i = 0}^{n}\sum_{j = 0}^{\left\lfloor\tfrac{ai + b}{c}\right\rfloor - 1}1 \\ & = \sum_{i = 0}^{n}\sum_{j = 0}^{m - 1}\left[j < \left\lfloor\dfrac{ai + b}{c}\right\rfloor\right] \\ & = \sum_{j = 0}^{m - 1}\sum_{i = 0}^{n}\left[j < \left\lfloor\dfrac{ai + b}{c}\right\rfloor\right] \\ & = \sum_{j = 0}^{m - 1}\sum_{i = 0}^{n}\left[i > t\right] \\ & = \sum_{j = 0}^{m - 1}\left(n - t\right) \\ & = \sum_{j = 0}^{m - 1}n + \sum\limits_{j = 0}^{m - 1}\left\lfloor\dfrac{cj + (c - b - 1)}{a}\right\rfloor \\ & = nm - f(c, c - b - 1, a, m - 1) \end{aligned} $$

综上所述,我们得到了 \(f\) 的递推式: $$ f(a, b, c, n) = \begin{cases} f(a \bmod c, b \bmod c, c, n) + \dfrac{n(n + 1)}{2}\cdot\left\lfloor\dfrac{a}{c}\right\rfloor + (n + 1)\cdot\left\lfloor\dfrac{b}{c}\right\rfloor & (a \ge n \lor b \ge n)\\ nm - f(c, c - b - 1, a, m - 1) & \textrm{otherwise} \end{cases} $$

g

我们 定义 \(g(a, b, c, n) = \sum_{i = 0}^{n}\left(i\cdot\left\lfloor\dfrac{ai + b}{c}\right\rfloor\right)\)

  • \(a \ge c\)\(b \ge c\) 时: $$ \begin{aligned} g(a, b, c, n) & = \sum_{i = 0}^{n}\left(i\cdot\left\lfloor\dfrac{ai + b}{c}\right\rfloor\right) \\ & = \sum_{i = 0}^{n}\left(i\cdot\left\lfloor\dfrac{\left(\left\lfloor\dfrac{a}{c}\right\rfloor\cdot c + a \bmod c\right) \cdot i + \left(\left\lfloor\dfrac{b}{c}\right\rfloor\cdot c + b \bmod c\right)}{c}\right\rfloor\right) \\ & = \sum_{i = 0}^{n}\left(i\cdot \left(\left\lfloor\dfrac{a}{c}\right\rfloor\cdot i + \left\lfloor\dfrac{b}{c}\right\rfloor\right) + i\cdot\left\lfloor\dfrac{\left(a \bmod c\right) \cdot i + \left(b \bmod c\right)}{c}\right\rfloor\right) \\ & = \left\lfloor\dfrac{a}{c}\right\rfloor\cdot\sum_{i = 0}^{n} i^2 + \left\lfloor\dfrac{b}{c}\right\rfloor\cdot\sum_{i = 0}^{n}i + \sum_{i = 0}^{n}\left(i\cdot\left\lfloor\dfrac{\left(a \bmod c\right) \cdot i + \left(b \bmod c\right)}{c}\right\rfloor\right) \\ & = \dfrac{n(n + 1)(2n + 1)}{6}\cdot\left\lfloor\dfrac{a}{c}\right\rfloor + (n + 1)\cdot\left\lfloor\dfrac{b}{c}\right\rfloor + g(a \bmod c, b \bmod c, c, n) \end{aligned} $$

  • \(a < c\)\(b < c\) 时: $$ \begin{aligned} g(a, b, c, n) & = \sum_{i = 0}^{n}\left(i\cdot\left\lfloor\dfrac{ai + b}{c}\right\rfloor\right) \\ & = \sum_{i = 0}^{n}i\cdot\left(\sum_{j = 0}^{\left\lfloor\tfrac{ai + b}{c}\right\rfloor - 1}1\right) \\ & = \sum_{i = 0}^{n}i\cdot\left(\sum_{j = 0}^{m}\left[j < \left\lfloor\dfrac{ai + b}{c}\right\rfloor\right]\right) \\ & = \sum_{j = 0}^{m - 1}i\cdot\sum_{i = 0}^{n}\left[i > t\right] \\ & = \sum_{j = 0}^{m - 1}\sum_{i = 0}^{n}\left[i > t\right]\cdot i \\ & = \sum_{j = 0}^{m - 1}\cdot\sum_{i = t + 1}^{n}1 \\ & = \sum_{j = 0}^{m - 1}\dfrac{(t + n + 1)(n - t)}{2} \\ & = \dfrac{1}{2}\sum_{j = 0}^{m - 1}\bigg(n(n + 1) - t^2 - t\bigg) \\ & = \dfrac{1}{2}mn(n + 1) - \dfrac{1}{2}\sum_{j = 0}^{m - 1}t^2 - \dfrac{1}{2}\sum_{j = 0}^{m - 1}t \\ & = \dfrac{1}{2}mn(n + 1) - \dfrac{1}{2}\sum_{j = 0}^{m - 1}\left(\left\lfloor\dfrac{cj + (c - b - 1)}{a}\right\rfloor\right)^2 - \dfrac{1}{2}\sum_{j = 0}^{m - 1}\left(\left\lfloor\dfrac{cj + (c - b - 1)}{a}\right\rfloor\right) \\ & = \dfrac{1}{2}mn(n + 1) - \dfrac{1}{2}h(c, c - b - 1, a, m - 1) - \dfrac{1}{2}g(c, c - b - 1, a, m - 1) \end{aligned} $$

综上所述,我们得到了 \(g\) 的递推式: $$ g(a, b, c, n) = \begin{cases} \dfrac{n(n + 1)(2n + 1)}{6}\cdot\left\lfloor\dfrac{a}{c}\right\rfloor + (n + 1)\cdot\left\lfloor\dfrac{b}{c}\right\rfloor + g(a \bmod c, b \bmod c, c, n) & (a \ge c \lor b \ge c) \\ \dfrac{1}{2}mn(n + 1) - \dfrac{1}{2}h(c, c - b - 1, a, m - 1) - \dfrac{1}{2}g(c, c - b - 1, a, m - 1) & \textrm{otherwise} \end{cases} $$

h

我们 定义 \(h(a, b, c, n) = \sum_{i = 0}^{n}\left(\left\lfloor\dfrac{ai + b}{c}\right\rfloor\right)^2\)

  • \(a \ge c\)\(b \ge c\) 时: $$ \begin{aligned} h(a, b, c, n) & = \sum_{i = 0}^{n}\left(\left\lfloor\dfrac{ai + b}{c}\right\rfloor\right)^2 \\ & = \sum_{i = 0}^{n}\left(\left\lfloor\dfrac{\left(\left\lfloor\dfrac{a}{c}\right\rfloor\cdot c + a \bmod c\right) \cdot i + \left(\left\lfloor\dfrac{b}{c}\right\rfloor\cdot c + b \bmod c\right)}{c}\right\rfloor\right)^2 \\ & = \sum_{i = 0}^{n}\left(\left\lfloor\dfrac{a}{c}\right\rfloor\cdot i + \left\lfloor\dfrac{b}{c}\right\rfloor + \left\lfloor\dfrac{\left(a \bmod c\right) \cdot i + \left(b \bmod c\right)}{c}\right\rfloor\right)^2 \\ & = \sum_{i = 0}^{n}\Bigg(\left(\left\lfloor\dfrac{a}{c}\right\rfloor\cdot i\right)^2 + \left(\left\lfloor\dfrac{b}{c}\right\rfloor\right)^2 + \left(\left\lfloor\dfrac{\left(a \bmod c\right) \cdot i + \left(b \bmod c\right)}{c}\right\rfloor\right)^2 \\ & + 2 \cdot \left(\left\lfloor\dfrac{a}{c}\right\rfloor\cdot i\right)\cdot\left(\left\lfloor\dfrac{b}{c}\right\rfloor\right) + 2 \cdot \left(\left\lfloor\dfrac{b}{c}\right\rfloor\right)\cdot\left\lfloor\dfrac{\left(a \bmod c\right) \cdot i + \left(b \bmod c\right)}{c}\right\rfloor \\ & + 2\cdot\left\lfloor\dfrac{\left(a \bmod c\right) \cdot i + \left(b \bmod c\right)}{c}\right\rfloor\cdot\left(\left\lfloor\dfrac{a}{c}\right\rfloor\cdot i\right)\Bigg) \\ & = \left(\left\lfloor\dfrac{a}{c}\right\rfloor\right)^2\sum_{i = 0}^{n} i^2 + 2\left\lfloor\dfrac{a}{c}\right\rfloor\cdot\left\lfloor\dfrac{b}{c}\right\rfloor\sum_{i = 0}^{n}i + \left(\left\lfloor\dfrac{b}{c}\right\rfloor\right)^2\sum_{i = 0}^{n}1 \\ & + \sum_{i = 0}^{n}\left(\left\lfloor\dfrac{\left(a \bmod c\right) \cdot i + \left(b \bmod c\right)}{c}\right\rfloor\right)^2 + 2\cdot\left\lfloor\dfrac{b}{c}\right\rfloor\sum_{i = 0}^{n}\left(\left\lfloor\dfrac{\left(a \bmod c\right) \cdot i + \left(b \bmod c\right)}{c}\right\rfloor\right) \\ & + 2\cdot\left\lfloor\dfrac{a}{c}\right\rfloor\sum_{i = 0}^{n}\left(i\cdot\left\lfloor\dfrac{\left(a \bmod c\right) \cdot i + \left(b \bmod c\right)}{c}\right\rfloor\right) \\ & = \dfrac{n(n + 1)(2n + 1)}{6}\cdot\left(\left\lfloor\dfrac{a}{c}\right\rfloor\right)^2 + n(n + 1)\cdot\left\lfloor\dfrac{a}{c}\right\rfloor\cdot\left\lfloor\dfrac{b}{c}\right\rfloor + (n + 1)\cdot\left(\left\lfloor\dfrac{b}{c}\right\rfloor\right)^2 \\ & + 2\cdot\left\lfloor\dfrac{b}{c}\right\rfloor f(a \bmod c, b \bmod c, c, n) + 2\cdot\left\lfloor\dfrac{a}{c}\right\rfloor g(a \bmod c, b \bmod c, c, n) + h(a \bmod c, b \bmod c, c, n) \end{aligned} $$

  • \(a < c\)\(b < c\) 时: $$ \begin{aligned} h(a, b, c, n) & = \sum_{i = 0}^{n}\left(\left\lfloor\dfrac{ai + b}{c}\right\rfloor\right)^2 \\ & = \sum_{i = 0}^{n}\left(2\cdot\dfrac{\left\lfloor\dfrac{ai + b}{c}\right\rfloor\cdot\left(\left\lfloor\dfrac{ai + b}{c}\right\rfloor + 1\right)}{2} - \left\lfloor\dfrac{ai + b}{c}\right\rfloor\right) \\ & = -f(a, b, c, n) + 2\sum_{i = 0}^{n}\sum_{j = 0}^{\left\lfloor\tfrac{ai + b}{c}\right\rfloor}j \\ & = -f(a, b, c, n) + 2\sum_{i = 0}^{n}\sum_{j = 1}^{\left\lfloor\tfrac{ai + b}{c}\right\rfloor}j \\ & = -f(a, b, c, n) + 2\sum_{i = 0}^{n}\sum_{j = 0}^{\left\lfloor\tfrac{ai + b}{c}\right\rfloor - 1}(j + 1) \\ & = -f(a, b, c, n) + 2\sum_{j = 0}^{m - 1}(j + 1)\sum_{i = 0}^{n}\left[j < \left\lfloor\dfrac{ai + b}{c}\right\rfloor\right] \\ & = -f(a, b, c, n) + 2\sum_{j = 0}^{m - 1}(j + 1)\sum_{i = 0}^{n}\left[i > t\right] \\ & = -f(a, b, c, n) + 2\sum_{j = 0}^{m - 1}(j + 1)(n - t) \\ & = -f(a, b, c, n) + 2n\sum_{j = 0}^{m - 1}(j + 1) - 2\sum_{j = 0}^{m - 1}(j + 1)t \\ & = -f(a, b, c, n) + nm(m + 1) - 2\sum_{j = 0}^{m - 1}jt - \sum_{j = 0}^{m - 1}t \\ & = -f(a, b, c, n) + nm(m + 1) - 2\sum_{j = 0}^{m - 1}\left(j\cdot\left\lfloor\dfrac{cj + c - b - 1}{a}\right\rfloor\right) - \sum_{j = 0}^{m - 1}\left\lfloor\dfrac{cj + c - b - 1}{a}\right\rfloor \\ & = -f(a, b, c, n) + nm(m + 1) - 2g(c, c - b - 1, a, m - 1) - 2f(c, c - b - 1, a, m - 1); \end{aligned} $$

综上所述,我们得到了 \(h\) 的递推式: $$ h(a, b, c, n) = \begin{cases} \dfrac{n(n + 1)(2n + 1)}{6}\cdot\left(\left\lfloor\dfrac{a}{c}\right\rfloor\right)^2 & + n(n + 1)\cdot\left\lfloor\dfrac{a}{c}\right\rfloor\cdot\left\lfloor\dfrac{b}{c}\right\rfloor + (n + 1)\cdot\left(\left\lfloor\dfrac{b}{c}\right\rfloor\right)^2 \\ & + 2\cdot\left\lfloor\dfrac{b}{c}\right\rfloor f(a \bmod c, b \bmod c, c, n) \\ & + 2\cdot\left\lfloor\dfrac{a}{c}\right\rfloor g(a \bmod c, b \bmod c, c, n) \\ & + h(a \bmod c, b \bmod c, c, n) & (a \ge c \lor b \ge c) \\ f(a, b, c, n) + nm(m + 1) & - 2g(c, c - b - 1, a, m - 1) \\ & - 2f(c, c - b - 1, a, m - 1) & \textrm{otherwise} \end{cases} $$

时间复杂度证明

不会。

代码实现

这里给出 【模板】类欧几里得算法 的代码实现。

 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
83
84
85
86
87
88
#include <bits/stdc++.h>
#define LL long long
#define LOCAL

namespace io {
    template <typename T> inline void read(T & _x) {
        int f = 0, ch; _x = 0;
        while(!isdigit(ch = getchar())) f |= ch == '-';
        while(isdigit(ch)) _x = _x * 10 + ch - '0', ch = getchar();
        if(f) _x = -_x;
    }
    template <typename T, typename ... Args> inline void read(T &_f, Args& ... args) {
        read(_f), read(args ...);
    }
    inline void _deal(char ch) { putchar(ch); }
    template <typename T> inline void _deal(T _x) {
        if (_x < 0) putchar('-'), _x = -_x;
        if (_x > 9) _deal(_x / 10);
        putchar(_x % 10 + '0');
    }
    inline void write() {}
    template <typename T, typename ... Args> inline void write(T _f, Args ... args) {
        _deal(_f), write(args...);
    }
}

const int mod = 998244353;
const int inv2 = 499122177;
const int inv6 = 166374059;

LL t, A, B, C, N;

struct QUERY {
    LL f, g, h;
};

QUERY solve(LL a, LL b, LL c, LL n) {
    QUERY res, tmp;
    if(!a) {
        res.f = (b / c) * (n + 1) % mod;
        res.g = (b / c) * inv2 % mod * n % mod * (n + 1) % mod;
        res.h = (b / c) * (b / c) % mod * (n + 1) % mod;
        return res;
    }
    else if(a >= c || b >= c) {
        tmp = solve(a % c, b % c, c, n);
        res.f = (tmp.f
              + (a / c) * inv2 % mod * n % mod * (n + 1) % mod
              + (b / c) * (n + 1) % mod) % mod;
        res.g = (tmp.g
              + (a / c) * inv6 % mod * n % mod * (n + 1) % mod * (2 * n + 1) % mod
              + (b / c) * inv2 % mod * n % mod * (n + 1) % mod) % mod;
        res.h = (tmp.h
              + (b / c) * 2 % mod * tmp.f % mod
              + (a / c) * 2 % mod * tmp.g % mod
              + (a / c) * (a / c) % mod * inv6 % mod * n % mod * (n + 1) % mod * (2 * n + 1) % mod
              + (b / c) * (b / c) % mod * (n + 1) % mod
              + (a / c) * (b / c) % mod * n % mod * (n + 1) % mod) % mod;
        return res;
    }
    else {
        LL m = (a * n + b) / c;
        tmp = solve(c, c - b - 1, a, m - 1);
        res.f = ((m * n % mod - tmp.f) % mod + mod) % mod;
        res.g = inv2 * (((m * n % mod * (n + 1) % mod
                        - tmp.f
                        - tmp.h) % mod + mod) % mod) % mod;
        res.h = ((n * m % mod * (m + 1) % mod
                - res.f
                - 2 * tmp.g % mod
                - 2 * tmp.f % mod) % mod + mod) % mod;
        return res;
    }
}

int main() {
#ifdef LOCAL
    freopen("sim.in", "r", stdin);
    freopen("sim.out", "w", stdout);
#endif
    io::read(t);
    while(t--) {
        io::read(N, A, B, C);
        QUERY cur = solve(A, B, C, N);
        io::write(cur.f, ' ', cur.h, ' ', cur.g, '\n');
    }
    return 0;
}