AtCoder Beginner Contest 443 题解

项目	内容
比赛时间	2026-01-31
比赛链接	https://atcoder.jp/contests/abc443
题目数量	A–G 共 7 题

比赛概览

本场整体难度较友好：A、B 为纯签到题；C 是一道按题意直接模拟的区间题；D 考察"相邻列行差不超过 1"这一约束的转化，用两遍扫描求下包络；E 是网格 DP，难点在于拆墙条件的判定；F 把"按位构造数字"转化为图上的最短路（BFS），并需要严谨论证"先到先得"能得到最小值；G 是经典的 floor sum（AtCoder Library 板子）计数题。其中 D、F、G 三道题较有区分度，分别考察约束传播、图论建模与数论板子，值得重点掌握。

---

A - Append s

题目链接：https://atcoder.jp/contests/abc443/tasks/abc443_a

题目大意

给定一个由小写英文字母组成的字符串 $S$（长度 $1 \le |S| \le 10$），在其末尾追加一个字符 s 并输出。

思路

直接在字符串末尾追加字符即可。这是最基础的签到题，C++ 里 s += 's' 一行完成，注意 +='s'（字符）与 +="s"（字符串）均可。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string S;
    cin >> S;
    S += 's';
    cout << S << '\n';
    return 0;
}

官方题解给出的 Python 参考实现：

s = input()
s += 's'
print(s)

复杂度分析

• 时间复杂度：$O(|S|)$
• 空间复杂度：$O(|S|)$

---

B - Setsubun

题目链接：https://atcoder.jp/contests/abc443/tasks/abc443_b

题目大意

节分这天，人们要吃掉与年龄相同数量的豆子。Takahashi 今年（第 $0$ 年后）$N$ 岁，每年节分他吃掉 $N+i$ 颗豆子（$i$ 年后）。他从今年起（含今年）最早到第几年之后，累计吃掉的豆子数达到 $K$ 颗或以上？$1 \le N,K \le 10^8$。

思路

第 $i$ 年他吃掉 $N+i$ 颗豆子，因此前 $i+1$ 年的累计为

$$\sum_{j=0}^{i}(N+j) = (i+1)N + \frac{i(i+1)}{2} = \frac{(i+1)(2N+i)}{2}.$$

直接按 $i=0,1,2,\dots$ 逐年累加模拟即可。为什么不会超时？ 最坏情况是 $N=1$（每年吃得最少）、$K=10^8$（目标最大），此时需要满足

$$\frac{(i+1)(i+2)}{2} \ge 10^8 \quad\Longrightarrow\quad i \approx \sqrt{2\times 10^8} \approx 14142,$$

即最多约 $1.4\times 10^4$ 次迭代，远小于时间限制。官方题解给出更宽松的估计：从 $1$ 岁开始吃 $10^5$ 年累计已超过 $5\times 10^9$ 颗。

进阶（可选）：也可以直接解二次不等式 $\frac{(i+1)(2N+i)}{2}\ge K$，即

$$i^2+(2N+1)i+(2N-2K)\ge 0,$$

其正根为

$$i_0 = \frac{-(2N+1)+\sqrt{(2N-1)^2+8K}}{2},$$

答案为 $\lceil i_0 \rceil$（用整数运算实现时注意浮点误差，可先取整再微调验证）。不过模拟循环已足够简单且高效。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll N, K;
    cin >> N >> K;
    ll total = 0;
    for (ll i = 0; ; i++) {
        total += N + i;
        if (total >= K) {
            cout << i << '\n';
            return 0;
        }
    }
}

复杂度分析

• 时间复杂度：$O(\sqrt K)$（约 $1.4\times 10^4$ 次迭代）
• 空间复杂度：$O(1)$

---

C - Chokutter Addiction

题目链接：https://atcoder.jp/contests/abc443/tasks/abc443_c

题目大意

AtCoder 公司从时刻 $0$ 开始上班、时刻 $T$ 结束。Takahashi 按照如下规则看 SNS chokutter：

• 上班开始时（时刻 $0$）打开 chokutter；
• 若 Aoki 经过他身后时 chokutter 正开着，他立刻关闭；
• 若他在时刻 $t$ 关闭，则一定在时刻 $t+100$ 重新打开。

上班期间 Aoki 共经过 $N$ 次，第 $i$ 次在时刻 $A_i$（满足 $0\le N \le 3\times10^5$，$1\le A_1<A_2<\dots<A_N\le T\le 10^9$，且保证 Aoki 不会在 Takahashi 打开 chokutter 的那一刻经过）。求 Takahashi 总共看了多少秒 chokutter。

思路

关键观察：Takahashi 的状态只可能是"开着"或"关着"，而"开着"的时间段总是从某个 open 时刻开始、到某次 Aoki 经过（或下班 $T$）结束；每次关闭后一定相隔 $100$ 秒重新打开，所以 open 的更新完全确定。

维护变量 $\mathit{open}$ 表示当前这轮打开 chokutter 的时刻。由于 $A$ 已经有序，按顺序扫描每次 Aoki 经过的时刻 $a$：

• 若 $\mathit{open} < a$：说明在 $a$ 时刻 chokutter 正开着，从 $\mathit{open}$ 到 $a$ 这一整段都在观看，累加 $a-\mathit{open}$，然后 Takahashi 立刻关闭，并把下一次打开时刻设为 $\mathit{open} \leftarrow a+100$；
• 否则（$\mathit{open} \ge a$）：说明 $a$ 时刻 chokutter 没开着（$a$ 落在两轮打开之间），Aoki 的经过不影响任何行为，什么都不做。

最后，如果 $\mathit{open} < T$，说明最后一轮从 $\mathit{open}$ 一直看到下班，累加 $T-\mathit{open}$。

正确性：每轮"打开 $\to$ 被 Aoki 关闭"的时间段互不重叠且完全覆盖所有观看时间；$\mathit{open}$ 精确记录了当前观看区间的左端点。易错点：$\mathit{open}$ 可能超过 $T$（例如样例 1 最后 $\mathit{open}=800>T=700$），此时收尾判断 $\mathit{open}<T$ 自然不成立，不会多加；$N=0$ 时答案为 $T$。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, T;
    cin >> N >> T;
    ll ans = 0;
    int open = 0;                     // 最近一次打开 chokutter 的时刻
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        if (open < a) {               // a 时刻正开着：从 open 看到 a
            ans += a - open;
            open = a + 100;           // 100 秒后重新打开
        }
        // 否则 a 时刻没开，什么都不发生
    }
    if (open < T) ans += T - open;    // 收尾：最后一轮看到下班
    cout << ans << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(N)$
• 空间复杂度：$O(1)$

---

D - Pawn Line

题目链接：https://atcoder.jp/contests/abc443/tasks/abc443_d

题目大意

有一个 $N\times N$ 的网格，每列恰好有一个棋子，列 $i$ 的棋子在从上往下第 $R_i$ 行。每次操作可以把一个不在最顶行的棋子向上移动一格（行号减 $1$）。求最少的操作次数，使得对所有 $1\le i\le N-1$，相邻两列棋子的行号满足 $|x_i-x_{i+1}|\le 1$。共 $T$ 组数据，$\sum N\le 3\times 10^5$。

思路

记列 $i$ 棋子的最终行号为 $x_i$。因为棋子只能向上移动，所以 $x_i\le R_i$。相邻约束 $|x_i-x_{i+1}|\le 1$ 逐段传递后给出任意两列之间的约束

$$|x_i-x_j|\le |i-j|,$$

于是对任意两列 $k,j$：

$$x_j\;\le\; x_k+|j-k|\;\le\; R_k+|j-k|.$$

这告诉我们：列 $j$ 的最终行号不能超过 $\min_{k}(R_k+|j-k|)$（其中 $k=j$ 时给出 $R_j$ 本身）。操作数等于 $\sum_i (R_i-x_i)$，要让操作数最小就要让每个 $x_i$ 尽量大。若记

$$B_j=\min_{k}\left(R_k+|j-k|\right),$$

那么 $x_j\le B_j$，并且（下面证明）向量 $B$ 本身满足相邻差不超过 $1$，即把每个棋子都移到 $B_j$ 行是可行的。因此最优方案就是 $x_j=B_j$，答案 $=\sum R_i-\sum B_j$。

如何高效计算 $B_j=\min_k(R_k+|j-k|)$？ 这是经典的一维"下包络/距离变换"，用两遍扫描：

1. 先从左到右：$B_i=\min(B_i,\ B_{i-1}+1)$，得到所有 $k\le i$ 的贡献 $\min_{k\le i}(R_k+i-k)$；
2. 再从右到左：$B_i=\min(B_i,\ B_{i+1}+1)$，把 $k>i$ 的贡献也纳入。

两遍后 $B_i$ 恰为 $\min_k(R_k+|i-k|)$。

为什么结果向量满足相邻差 $\le 1$？ 第一遍结束后满足 $B_{i-1}+1\ge B_i$（即 $B_i\le B_{i-1}+1$）。第二遍考虑操作 $B_i=\min(B_i,B_{i+1}+1)$：若 $B_i$ 被更新，则 $B_i=B_{i+1}+1$，相邻差恰好为 $1$；若未被更新，则 $B_i\le B_{i+1}+1$，而第二遍只会让 $B_{i+1}$ 变小，第一遍保证的 $B_i+1\ge B_{i+1}$ 不会被破坏，两者合起来得 $B_{i+1}-1\le B_i\le B_{i+1}+1$。因此 $B$ 满足题目条件，且它是所有合法方案中每列行号的最大值，故为最优。

易错点：$R_i$ 之和可能达到 $N^2\approx 9\times 10^{10}$，要用 64 位整数。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        vector<ll> R(N);
        ll sum = 0;
        for (int i = 0; i < N; i++) {
            cin >> R[i];
            sum += R[i];
        }
        // 从左到右：传播"左边棋子"的约束
        for (int i = 1; i < N; i++) R[i] = min(R[i], R[i - 1] + 1);
        // 从右到左：传播"右边棋子"的约束
        for (int i = N - 2; i >= 0; i--) R[i] = min(R[i], R[i + 1] + 1);
        for (int i = 0; i < N; i++) sum -= R[i];
        cout << sum << '\n';
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(N)$（每组数据）
• 空间复杂度：$O(N)$

---

E - Climbing Silver

题目链接：https://atcoder.jp/contests/abc443/tasks/abc443_e

题目大意

有一个 $N\times N$ 网格，$(i,j)$ 为墙（#）或空地（.）。Takahashi 初始在空地 $(N,C)$，然后重复 $N-1$ 次移动：从 $(r,c)$ 出发，目的地取 $(r-1,c-1),(r-1,c),(r-1,c+1)$ 之一（不能出界）。若目的地是墙：

• 当该列在目的地下方的所有格子 $(i,b)\ (a<i\le N)$ 当前都是空地时，可以拆掉这面墙并移动过去；
• 否则移动失败，立刻终止（即使还没走满 $N-1$ 步）。

输出一个长度为 $N$ 的 $0/1$ 串 $R$：若他能无失败地到达 $(1,i)$，则第 $i$ 位为 1，否则为 0。共 $T$ 组数据，$\sum N^2\le 9\times 10^6$，$N\le 3000$。

思路

用 DP 记录可达性。定义 $dp[i][j]=1$ 表示 Takahashi 能无失败地到达格子 $(i,j)$。

初始化：对所有 $i$ 置 $dp[i][C]=1$。因为起点 $(N,C)$ 是空地，他可以沿列 $C$ 自下而上逐格移动：遇到墙时，其下方的格子都已经被他走过/拆过成为空地，故总能满足拆墙条件。

转移：从下往上处理行 $i=N-2,N-3,\dots,0$。若 $dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1]$ 三者中至少一个为 $1$，说明"不考虑墙"时 $(i,j)$ 可达：

• 若 $(i,j)$ 是空地，直接 $dp[i][j]=1$；
• 若 $(i,j)$ 是墙，则只有当它是该列最下方的墙时才能拆。为此预处理 $low[j]$ 表示第 $j$ 列中最靠下（行号最大）的墙所在行。拆墙条件"$(i,j)$ 下方全空"等价于 $low[j]=i$（$i$ 行以下是该列最下方的墙，下面全是空地）。一旦拆掉 $(i,j)$ 并站上去，他可以继续沿列向上推进、把上方的墙逐块拆掉，因此整列从第 $i$ 行到顶全都可达：令 $dp[k][j]=1$ 对所有 $0\le k\le i$。

正确性：拆墙条件只与原始网格中"该列 $i$ 行以下是否有墙"有关——若下方原本有空地被走过、或有墙被拆掉，那么被拆掉的墙在拆的时候已经把其上方的格子标为可达（即 $dp[i][j]$ 早已为 $1$），不会等到现在才需要处理。因此对墙的处理只需判断 $low[j]==i$ 这一次；每列至多被"整列标记"一次，总工作量 $O(N^2)$。

易错点：$j-1$、$j+1$ 越界判断；$dp[i][j]$ 可能已被更下方的拆墙标记为 $1$，此时要直接跳过（continue），否则会重复处理。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int N, C;
        cin >> N >> C;
        C--;
        vector<string> S(N);
        vector<int> low(N, -1);
        for (int i = 0; i < N; i++) {
            cin >> S[i];
            for (int j = 0; j < N; j++)
                if (S[i][j] == '#') low[j] = i;  // 列 j 中最靠下的墙的行号
        }
        vector<vector<int>> dp(N, vector<int>(N, 0));
        for (int i = 0; i < N; i++) dp[i][C] = 1;  // 沿列 C 直上一定可行
        for (int i = N - 2; i >= 0; i--) {
            for (int j = 0; j < N; j++) {
                if (dp[i][j]) continue;            // 已被下方拆墙标为可达
                bool ok = dp[i + 1][j];
                if (j > 0 && dp[i + 1][j - 1]) ok = true;
                if (j + 1 < N && dp[i + 1][j + 1]) ok = true;
                if (!ok) continue;
                if (S[i][j] == '.') {
                    dp[i][j] = 1;
                } else if (low[j] == i) {          // 是该列最下方的墙，可拆
                    for (int k = 0; k <= i; k++) dp[k][j] = 1;
                }
            }
        }
        for (int j = 0; j < N; j++) cout << dp[0][j];
        cout << '\n';
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(N^2)$（每组数据；每列至多整列标记一次，均摊后仍为 $O(N^2)$）
• 空间复杂度：$O(N^2)$

---

F - Non-Increasing Number

题目链接：https://atcoder.jp/contests/abc443/tasks/abc443_f

题目大意

称正整数 $X$ 是好整数，当且仅当它写成十进制后，从个位到最高位的数字序列 $d_0,d_1,d_2,\dots$（满足 $X=\sum_i d_i10^i$）是非递增的，即 $d_0\ge d_1\ge d_2\ge\dots$。例如 $112389$、$1$、$777$ 是好整数，$443$、$404$ 不是。

给定正整数 $N$（$1\le N\le 3\times 10^6$），判断是否存在 $N$ 的好整数倍，若存在输出最小值，否则输出 $-1$。答案可能非常大（样例 4 给出了 22 位的答案）。

思路

第一步：重述题意。 条件 $d_0\ge d_1\ge d_2\ge\dots$（个位最大）等价于从左往右读数字是非递减的（最高位最小）。例如 $126$：$1\le2\le6$。另一个重要事实：好整数的每一位都在 $\{1,2,\dots,9\}$ 中——若某一位出现 $0$，则比它更低的所有位也都必须是 $0$，整个数就是 $0$，不可能是正整数。

第二步：转化为图上最短路。 把数字从高位到低位一位一位地构造。状态设为二元组 $(x,c)$：

• $x$：当前已构造的数模 $N$ 的余数；
• $c$：当前构造出的数的最低位（最后追加的那一位）。

由于数字从左到右非递减，接下来追加的位 $cc$ 必须满足 $cc\ge c$；追加后新的余数为 $x'=(10x+cc)\bmod N$，新的最低位为 $cc$。于是得到一个有向图：

$$(x,c)\;\longrightarrow\;\bigl((10x+cc)\bmod N,\ cc\bigr),\qquad cc=c,c+1,\dots,9,$$

起点是 $(0,0)$（$c=0$ 表示还没有任何数字，因此第一位必须 $\ge 1$，即 $cc=1,\dots,9$）。每条边代表"多一位数字"，花费均为 $1$。

第三步：为什么 BFS 能给出最小值。 我们要求的是能被 $N$ 整除的最小好整数，即从起点到达某个 $x=0$ 的状态 $(0,c)$ 的"位数最少、且数值最小"的路径。

• 位数最少：更多位数一定数值更大，所以先做 BFS（边权全为 $1$）保证找到的是位数最少的答案；
• 数值最小：对固定位数的数，数值大小等于从左到右的字典序大小。BFS 从每个状态出发按 $cc$ 升序尝试，且队列先进先出，因此同位数的好整数是按从小到大（字典序）依次被发现的。于是第一个到达 $x=0$ 的状态对应的数字就是全局最小答案。

用数组 $to$ 记录每个状态的转移来源（父状态），找到答案后沿着 $to$ 一路回溯，把路径上每个状态的编号 $\bmod 10$（即当时追加的那一位）收集起来再反转即可得到答案串。若队列耗尽仍未到达 $x=0$，输出 $-1$。

关于 $-1$ 的说明：最显然的无解情形是 $N$ 为 $10$ 的倍数——此时任何倍数都以 $0$ 结尾，而好整数不含数字 $0$。但无解并不只限于此（例如 $N=275$ 也无解，可以用模 $25$、$11$ 的条件推出来），BFS 会自然检测到：状态空间有限（$10N$ 个状态），全部可达状态遍历完后仍无 $x=0$，即为 $-1$。

一个优化（官方题解的写法）：扩展状态 $(x,c)$ 时按 $cc=c,c+1,\dots,9$ 升序尝试，一旦发现目标状态 $(10x+cc\bmod N,\ cc)$ 已经访问过，就立刻 break，不再尝试更大的 $cc$。正确性在于：若追加 $cc$ 的目标已访问，说明它是由某个更早被处理的状态 $p$ 通过追加数字 $cc$ 到达的（由同余结构，$p$ 与当前状态满足 $10p.x\equiv 10x\pmod N$），而 $p$ 被处理得更早，它当时继续尝试更大数字产生的后继——与我们想跳过的后继完全一致（因为 $(10x+cc')\bmod N=(10p.x+cc')\bmod N$）——要么已被 $p$ 入队，要么在更早时刻就已命中"目标已访问"的情形而继续归纳成立。因此跳过这些后继不会遗漏任何可达状态。若不想依赖这个证明，把 break 改成 continue 也同样正确（此时每个状态至多尝试 9 个数字，总复杂度 $O(N\cdot 10\cdot 9)=O(N)$，$\sigma=10$ 是常数）。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    // 状态编号 10*x + c：当前数值模 N 为 x，最低位数字为 c
    // to[v] = 状态 v 的转移来源，-1 表示未访问
    vector<int> to(10LL * N + 10, -1);
    deque<int> q;
    q.push_back(0);                       // 初始状态 (0, 0)
    while (!q.empty()) {
        int idx = q.front();
        q.pop_front();
        int c = idx % 10, x = idx / 10;
        // 下一位 cc >= 当前最低位 c（数字从左到右非递减）
        for (int cc = max(1, c); cc <= 9; cc++) {
            int xx = (int)((10LL * x + cc) % N);
            int idx2 = 10 * xx + cc;
            if (to[idx2] != -1) break;    // 已访问：更大的数字后继也已访问，剪枝
            to[idx2] = idx;
            q.push_back(idx2);
            if (xx == 0) {                // 第一个到达 x=0 的状态即最小答案
                string ans;
                int cur = idx2;
                while (cur != 0) {
                    ans.push_back(char('0' + cur % 10));
                    cur = to[cur];
                }
                reverse(ans.begin(), ans.end());
                cout << ans << '\n';
                return 0;
            }
        }
    }
    cout << -1 << '\n';
    return 0;
}

官方题解给出的 Python 参考实现（用 $to$ 同时承担"是否访问过"与"父状态"两个角色）：

from collections import deque

n = int(input())
to = [-1] * (10 * n)
q = deque([0])
while q:
    idx = q.popleft()
    c, x = idx % 10, idx // 10
    for cc in range(max(1, c), 10):
        xx = (10 * x + cc) % n
        idx2 = 10 * xx + cc
        if to[idx2] != -1:
            break
        q.append(idx2)
        to[idx2] = idx
        if xx == 0:
            ans = []
            cur = idx2
            while cur != 0:
                ans.append(str(cur % 10))
                cur = to[cur]
            print("".join(ans[::-1]))
            exit()
print(-1)

复杂度分析

• 时间复杂度：$O(N\sigma)$，其中 $\sigma=10$（状态数为 $10N$，每个状态至多尝试 $\sigma$ 个数字；不采用 break 时也为 $O(N\sigma^2)=O(N)$ 量级）
• 空间复杂度：$O(N\sigma)$（$to$ 数组与队列）

---

G - Another Mod of Linear Problem

题目链接：https://atcoder.jp/contests/abc443/tasks/abc443_g

题目大意

给定整数 $N,M,A,B$，定义数列 $X_k=(Ak+B)\bmod M$。求满足 $0\le k<N$ 且 $X_k>k$ 的 $k$ 的个数。共 $T$ 组数据，$1\le N\le M\le 10^9$，$0\le A,B<M$。

思路

设 $X=(Ak+B)\bmod M=Ak+B-M\left\lfloor\frac{Ak+B}{M}\right\rfloor$。条件 $k<X$ 可作如下等价变形：

$$\begin{aligned} k<(Ak+B)\bmod M &\iff k+1\le Ak+B-M\left\lfloor\frac{Ak+B}{M}\right\rfloor\\ &\iff \left\lfloor\frac{Ak+B}{M}\right\rfloor\le \frac{(A-1)k+(B-1)}{M}\\ &\iff \left\lfloor\frac{Ak+B}{M}\right\rfloor\le \left\lfloor\frac{(A-1)k+(B-1)}{M}\right\rfloor. \end{aligned}$$

其中第一步是因为两侧都是整数，$k<X$ 等价于 $k+1\le X$；最后一步用到了"对实数 $x$ 和整数 $X$，$X\le x$ 与 $X\le\lfloor x\rfloor$ 等价"。

记

$$D_k=\left\lfloor\frac{Ak+B}{M}\right\rfloor-\left\lfloor\frac{(A-1)k+(B-1)}{M}\right\rfloor.$$

注意到两个分数的差为

$$\frac{Ak+B}{M}-\frac{(A-1)k+(B-1)}{M}=\frac{k+1}{M}\in(0,1],$$

（因为 $0\le k<N\le M$），所以两个整数取整后至多相差 $1$，即 $D_k\in\{0,1\}$。于是指示量

$$[k<(Ak+B)\bmod M]\;=\;1-D_k.$$

对 $k=0,1,\dots,N-1$ 求和：

$$\text{答案}=N-\sum_{k=0}^{N-1}\left\lfloor\frac{Ak+B}{M}\right\rfloor+\sum_{k=0}^{N-1}\left\lfloor\frac{(A-1)k+(B-1)}{M}\right\rfloor.$$

这两个求和正是经典的 floor sum：$F(n,m,a,b)=\sum_{i=0}^{n-1}\left\lfloor\frac{ai+b}{m}\right\rfloor$，可以用欧几里得式的递归/迭代在 $O(\log m)$ 内求出（AtCoder Library 的 floor_sum 板子）。其核心思想是当 $a\ge m$ 或 $b\ge m$ 时先取出整除部分，再通过"交换 $m$ 与 $a$"把问题规模按欧几里得算法缩小。

注意：当 $A=0$ 或 $B=0$ 时，$A-1=-1$ 或 $B-1=-1$ 是负数。实现时要先把 $a,b$ 用带余除法归一化到 $[0,m)$：$a=q_a m+r_a\ (0\le r_a<m)$，则

$$\left\lfloor\frac{ai+b}{m}\right\rfloor=q_a i+\left\lfloor\frac{r_ai+b}{m}\right\rfloor,$$

对 $b$ 同理；把 $\sum q_a i=q_a\cdot\frac{n(n-1)}{2}$ 与 $q_b\cdot n$ 累加进答案后再调用非负版 floor_sum 即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// sum_{i=0}^{n-1} floor((a*i + b) / m)，要求 a, b >= 0（ACL 风格的 floor_sum，O(log m)）
ll floor_sum(ll n, ll m, ll a, ll b) {
    ll ans = 0;
    while (true) {
        if (a >= m) {
            ans += (n - 1) * n * (a / m) / 2;
            a %= m;
        }
        if (b >= m) {
            ans += n * (b / m);
            b %= m;
        }
        ll y_max = a * n + b;
        if (y_max < m) break;
        n = y_max / m;
        b = y_max % m;
        swap(m, a);
    }
    return ans;
}

// 允许 a, b 为负数的封装（本题 A-1、B-1 可能为 -1）
ll floor_sum_signed(ll n, ll m, ll a, ll b) {
    ll extra = 0;
    ll qa = a / m, ra = a % m;
    if (ra < 0) { ra += m; qa--; }              // 归一化 a 到 [0, m)
    extra += qa * (n * (n - 1) / 2);
    ll qb = b / m, rb = b % m;
    if (rb < 0) { rb += m; qb--; }              // 归一化 b 到 [0, m)
    extra += qb * n;
    return extra + floor_sum(n, m, ra, rb);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        ll N, M, A, B;
        cin >> N >> M >> A >> B;
        ll ans = N - floor_sum_signed(N, M, A, B)
                   + floor_sum_signed(N, M, A - 1, B - 1);
        cout << ans << '\n';
    }
    return 0;
}

官方题解给出的 Python 参考实现（递归版 floor_sum，Python 整除自带向下取整语义，天然支持负数）：

import sys
input = sys.stdin.readline

def floor_sum(n, m, a, b):
    a1, a2 = a // m, a % m
    s = n * (n - 1) // 2 * a1
    b1, b2 = b // m, b % m
    if a2 == 0:
        return s + b1 * n
    k = (a2 * (n - 1) + b2) // m
    return s + n * (k + b1) - floor_sum(k, a2, m, m + a2 - b2 - 1)

for _ in range(int(input())):
    n, m, a, b = map(int, input().split())
    print(n - floor_sum(n, m, a, b) + floor_sum(n, m, a - 1, b - 1))

复杂度分析

• 时间复杂度：$O(\log M)$（每组数据，floor sum 按欧几里得算法每次把规模减小约一半）
• 空间复杂度：$O(1)$（迭代版）/ $O(\log M)$（递归版栈深）