本文是以 oi-wiki 为基础，自己手 $\LaTeX$ 整理的式子；和本博客、oi-wiki 原文一样遵循 CC BY-SA 4.0 协议。

洛谷板题【模板】类欧几里得算法。

设

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

其中 $a, b, c, n$ 是常数。需要一个 $O(\log n)$ 的算法。

若 $a \ge c$ 或者 $b \ge c$，则可以将 $a$ 或 $b$ 对 $c$ 取模以简化问题：

$$\begin{align} f(a, b, c, n) &= \sum_{i = 0}^n{ \left\lfloor \frac{ai + b}c \right\rfloor} \\ &= \sum_{i = 0}^n{ \left\lfloor \frac{ \left( \lfloor a / c \rfloor c + a \bmod c \right) i + ( \lfloor b / c \rfloor c + b \bmod c )}c \right\rfloor} \\ &= \frac{n(n + 1)}2 \left\lfloor \frac ac \right\rfloor + (n + 1) \left\lfloor \frac bc \right\rfloor + \sum_{i = 0}^n{ \left\lfloor \frac{ (a \bmod c )i + (b \bmod c )}c \right\rfloor} \\ &= \frac{n(n + 1)}2 \left\lfloor \frac ac \right\rfloor + (n + 1) \left\lfloor \frac bc \right\rfloor + f(a \bmod c, b \bmod c, c, n) \end{align}$$

那么问题转化为了 $a < c, b < c$ 的情况。令 $m = \lfloor (an + b) / c\rfloor, t = \lfloor (cj + c - b - 1) / a \rfloor$，则

$$\begin{align} f(a, b, c, n) &= \sum_{i = 0}^n{ \left\lfloor \frac{ai + b}c \right\rfloor} \\ &= \sum_{i = 0}^n{ \sum_{j = 0}^{ \lfloor (ai + b) / c\rfloor - 1} 1 } \\ &= \sum_{j = 0}^{m - 1}{ \sum_{i = 0}^ n{ \left[ j < \left\lfloor \frac{ai + b}c \right\rfloor \right]}} \\ &= \sum_{j = 0}^{m - 1}{ \sum_{i = 0}^ n{ \left[ j + 1 \le \left\lfloor \frac{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)} \\ &= nm - f(c, c - b - 1, a, m - 1) \end{align}$$

复杂度为 $O(\log n)$。

---

设

$$g(a, b, c, n) = \sum_{i = 0}^n{i \left\lfloor \frac{ai + b}c \right\rfloor} \\ g(a, b, c, n) = g(a \bmod c, b \bmod c, c, n) + \left\lfloor \frac ac \right\rfloor \frac{n(n + 1)(2n + 1)}6 + \left\lfloor \frac bc \right\rfloor \frac{n(n + 1)}2$$

令 $m = \lfloor (an + b) / c\rfloor, t = \lfloor (cj + c - b - 1) / a \rfloor$，则

$$\begin{align} g(a, b, c, n) &= \sum_{i = 0}^n{ i \left\lfloor \frac{ai + b}c \right\rfloor} \\ &= \sum_{i = 0}^n{ \sum_{j = 0}^{ \lfloor (ai + b) / c\rfloor - 1} i } \\ &= \sum_{j = 0}^{m - 1}{ \sum_{i = 0}^ n{ i \left[ j < \left\lfloor \frac{ai + b}c \right\rfloor \right]}} \\ &= \sum_{j = 0}^{m - 1}{ \sum_{i = 0}^ n{ i \left[ j + 1 \le \left\lfloor \frac{ai + b}c \right\rfloor \right]}} \\ &= \sum_{j = 0}^{m - 1}{ \sum_{i = 0}^ n{ i \left[ i > t \right]}} \\ &= \sum_{j = 0}^{m - 1}{ \frac 12 (t + n + 1)(n - t)} \\ &= \frac 12 (mn(n + 1) - \sum_{j = 0}^{m - 1}t^2 - \sum_{j = 0}^{m - 1}t) \\ &= \frac 12 (mn(n + 1) - h(c, c - b - 1, a, m - 1) - f(c, c - b - 1, a, m - 1)) \end{align}$$

---

设

$$h(a, b, c, n) = \sum_{i = 0}^n{ \left\lfloor \frac{ai + b}c \right\rfloor^2} \\ \begin{align} h(a, b, c, n) = \ & h(a \bmod c, b \bmod c, c, n) \\ &+ 2 \left\lfloor \frac bc \right\rfloor f(a \bmod c, b \bmod c, c, n) + 2 \left\lfloor \frac ac \right\rfloor g(a \bmod c, b \bmod c, c, n) \\ &+ \left\lfloor \frac ac \right\rfloor^2 \frac{n(n + 1)(2n + 1)}6 + \left\lfloor \frac bc \right\rfloor^2 (n + 1) + \left\lfloor \frac ac \right\rfloor \left\lfloor \frac bc \right\rfloor n(n + 1) \end{align}$$

令 $m = \lfloor (an + b) / c\rfloor, t = \lfloor (cj + c - b - 1) / a \rfloor$。又有

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

则

$$\begin{align} h(a, b, c, n) &= \sum_{i = 0}^n{ \left\lfloor \frac{ai + b}c \right\rfloor^2} \\ &= \sum_{i = 0}^n{\left( \left( 2 \sum_{j = 0}^{ \lfloor (ai + b) / c \rfloor - 1}{(j + 1)} \right) - \left\lfloor \frac{ai + b}c \right\rfloor \right)} \\ &= 2 \sum_{i = 0}^n{ \sum_{j = 0}^{ \lfloor (ai + b) / c \rfloor - 1}{(j + 1)}} - f(a, b, c, n) \\ \sum_{i = 0}^n{ \sum_{j = 0}^{ \lfloor (ai + b) / c \rfloor - 1}{(j + 1)}} &= \sum_{j = 0}^{m - 1}{(j + 1) \sum_{i = 0}^n{\left[ j < \left\lfloor \frac{ai + b}c \right\rfloor \right]}} \\ &= \sum_{j = 0}^{m - 1}{(j + 1) \sum_{i = 0}^n{[i > t]}} \\ &= \sum_{j = 0}^{m - 1}{(j + 1)(n - t)} \\ &= \frac 12 nm(m + 1) - \sum_{j = 0}^{m - 1}{t(j + 1)} \\ h(a, b, c, n) &= nm(m + 1) - 2g(c, c - b - 1, a, m - 1) \\ & \quad - 2f(c, c - b - 1, a, m - 1) - f(a, b, c, n) \end{align}$$

---

三个函数一起递归计算，总复杂度 $O(\log n)$。

---

关于代码，由于我过懒，想用不定参解决，于是研究了 c++ 的不定参写法，浪费了更多时间。

板题最终代码（全是式子，看看就行，注意询问顺序 $f, h, g$）：

using ll = long long;

constexpr int mod = 998244353, inv2 = 499122177, inv6 = 166374059;

int Add(ll t) {
  return (t % mod + mod) % mod;
}

template<typename... Ts>
int Add(ll t, Ts... r) {
  return ((t + Add(r...)) % mod + mod) % mod;
}

int Mul(ll t) {
  return t % mod;
}

template<typename... Ts>
int Mul(ll t, Ts... r) {
  return (t * Mul(r...)) % mod;
}

struct Node {
  int f, g, h;

  Node() {}

  Node(int F, int G, int H): f(F), g(G), h(H) {}
};

Node solve(ll N, int a, int b, int c) {
  int fac = a / c, fbc = b / c;
  ll m = (1ll * a * N + b) / c, Np = N + 1, N2p = N << 1 | 1;
  if (!a) return Node(Mul(fbc, Np), Mul(fbc, N, Np, inv2), Mul(fbc, fbc, Np));

  Node z, y;
  if (a >= c || b >= c) {
    z.f = Add(Mul(N, Np, inv2, fac), Mul(fbc, Np));
    z.g = Add(Mul(fac, N, Np, N2p, inv6), Mul(fbc, N, Np, inv2));
    z.h = Add(Mul(fac, fac, N, Np, N2p, inv6), Mul(fbc, fbc, Np), Mul(fac, fbc, N, Np));
    y = solve(N, a % c, b % c, c);
    z.f = Add(z.f, y.f);
    z.g = Add(z.g, y.g);
    z.h = Add(z.h, y.h, Mul(2, fbc, y.f), Mul(2, fac, y.g));
    return z;
  }

  y = solve(m - 1, c, c - b - 1, a);
  z.f = Add(Mul(N, m), -y.f);
  z.g = Mul(Add(Mul(N, m, Np), -y.f, -y.h), inv2);
  z.h = Add(Mul(N, m, m + 1), -2 * y.g, -2 * y.f, -z.f);
  return z;
}

int main() {
  int T;
  Node ans;

  cin >> T;
  for (int N, a, b, c; T; --T) {
    cin >> N >> a >> b >> c;
    ans = solve(N, a, b, c);
    cout << ans.f << ' ' << ans.h << ' ' << ans.g << '\n';
  }
  return 0;
}