AtCoder Beginner Contest 423 题解

项目	内容
比赛时间	2025-09-14
比赛链接	https://atcoder.jp/contests/abc423
题目数量	A–G 共 7 题

比赛概览

本场整体难度偏低，A、B 为送分题，C 是带点思维的贪心/区间构造，D 是经典的"优先队列模拟排队"，E 是"换贡献视角 + 前缀和"的数学题（有一定区分度），F 是子集容斥（$N \le 20$ 强烈暗示 $2^N$ 枚举），G 是全场最难，综合了数论（模逆元、欧拉定理）、枚举与字符串比较。建议重点掌握 C、D、E、G 的思路。

---

A - Scary Fee

题目链接：https://atcoder.jp/contests/abc423/tasks/abc423_a

题目大意

账户余额为 $X$ 日元。取款金额必须为 $1000$ 日元的整数倍，并且每取 $1000$ 日元需额外支付 $C$ 日元手续费（手续费也从余额中扣除），取款后余额不能为负。求最多能取出多少钱。输入格式：一行两个整数 $X\ C$。

思路

设取款金额为 $1000m$ 日元（$m$ 为非负整数），则手续费为 $Cm$ 日元，取款的总花费为

$$1000m + Cm = (1000 + C)\,m.$$

要求总花费不超过余额 $X$，即 $(1000 + C)m \le X$。要使取款金额 $1000m$ 最大，就要取满足该不等式的最大的整数 $m$：

$$m_{\max} = \left\lfloor \frac{X}{1000 + C} \right\rfloor.$$

答案即为 $1000m_{\max}$。

正确性：取款金额每增加 $1000$，总花费增加 $1000 + C$ 日元，因此能取到的最大的千元整数倍就是 $X$ 除以 $(1000 + C)$ 的商再乘 $1000$。

易错点：

• $m_{\max}$ 可能为 $0$（当 $X < 1000 + C$ 时），此时答案是 $0$，即一分钱也取不出来，如样例 2。
• 手续费是按"每 $1000$ 日元"计收的，取款 $1000m$ 的手续费恰好为 $Cm$，不存在四舍五入，直接整数乘法即可。

参考代码

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

int main() {
    int x, c;
    cin >> x >> c;
    cout << (x / (1000 + c)) * 1000 << '\n';
    return 0;
}

复杂度分析

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

---

B - Locked Rooms

题目链接：https://atcoder.jp/contests/abc423/tasks/abc423_b

题目大意

$N+1$ 个房间 $0,1,\ldots,N$ 排成一行，门 $i$ 位于房间 $i-1$ 与 $i$ 之间。$L_i = 0$ 表示门开着，$L_i = 1$ 表示门锁着。有两个人分别从房间 $0$ 和房间 $N$ 出发，只能通过开着的门移动。求两人都无法到达的房间数量。输入格式：第一行 $N$，第二行 $L_1\ L_2\ \ldots\ L_N$。

思路

设 $X$ 为最左边锁着的门的编号，即最小的 $i$ 使 $L_i = 1$；设 $Y$ 为最右边锁着的门的编号，即最大的 $i$ 使 $L_i = 1$。

• 从房间 $0$ 出发的人被门 $X$ 挡住，能到达房间 $0,1,\ldots,X-1$；
• 从房间 $N$ 出发的人被门 $Y$ 挡住，能到达房间 $Y,Y+1,\ldots,N$；

于是两把"最外侧的锁"之间的房间 $X, X+1, \ldots, Y-1$ 恰好是两人都到不了的部分，数量为 $Y - X$ 个。

需要特判：若所有 $L_i = 0$（没有任何锁），则所有人都能到达全部房间，答案为 $0$。此时 $X, Y$ 不存在，代码中用 $X=-1$ 表示并单独输出 $0$。

边界情况：若 $X = Y$（只有一扇锁着的门），则中间房间数为 $Y - X = 0$，答案为 $0$，这由公式自然得到，无需特殊处理。

参考代码

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

int main() {
    int n;
    cin >> n;
    vector<int> l(n);
    for (int i = 0; i < n; i++) cin >> l[i];

    int x = -1, y = -1;
    for (int i = 0; i < n; i++) {
        if (l[i] == 1) { x = i; break; }
    }
    for (int i = n - 1; i >= 0; i--) {
        if (l[i] == 1) { y = i; break; }
    }

    cout << (x == -1 ? 0 : y - x) << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$（存储 $L$；若不存数组也可 $O(1)$ 边读边记）

---

C - Lock All Doors

题目链接：https://atcoder.jp/contests/abc423/tasks/abc423_c

题目大意

$N+1$ 个房间 $0,1,\ldots,N$ 排成一行，门 $i$ 位于房间 $i-1$ 与 $i$ 之间，$L_i = 0$ 开门、$L_i = 1$ 锁门。高桥初始在房间 $R$，只能在开着的门之间移动；他可以对门 $i$ 执行切换操作（开变锁、锁变开），但只有当他在房间 $i-1$ 或 $i$ 中时才能对门 $i$ 操作。求使所有门都锁上所需的最少切换次数。输入格式：第一行 $N\ R$，第二行 $L_1\ldots L_N$。$N \le 2 \times 10^5$。

思路

先做两个定义。 对开着的门做一次切换（使其锁上）称为锁门操作；对锁着的门做一次切换（使其打开）称为开门操作。注意只有移动不消耗次数，切换才消耗次数。

关键观察 1：可以假设所有开门操作先于所有锁门操作执行。 因为若某扇门最终要回到"锁上"状态，把对该门需要的开门操作全部提前到最前面，只会让途中可到达的门更多（不可能破坏可行性），而不会改变操作总数。由此每扇门至多被"开一次 + 锁一次"。

关键观察 2：设开门操作总数为 $t$，初始开着的门数为 $\mathrm{open}$，则锁门操作数必为 $\mathrm{open} + t$。 理由：

• 每扇初始开着的门最终必须锁上，至少需要 $1$ 次锁门操作；
• 每扇被打开（原本锁着）的门打开后还要再锁上，即每次开门操作都对应额外 $1$ 次锁门操作。

因此总操作数 = 锁门操作数 + 开门操作数 = $\mathrm{open} + 2t$，问题转化为最小化需要打开的锁着的门数 $t$。

关键观察 3：在执行完所有开门操作后，所有"此刻开着"的门必须构成一个连续区间 $[X, Y]$，并且该区间要包含与房间 $R$ 相邻的门，即满足 $X \le R$ 且 $R-1 \le Y$。 因为高桥只能沿直线移动，他当前能到达的区域永远是连续的；为了最终能走到每一扇开着的门前把它锁上，开门的集合必须是这样的一个区间。（门 $R-1$ 在房间 $R-2$ 与 $R-1$ 之间，门 $R$ 在房间 $R-1$ 与 $R$ 之间，它们是房间 $R$ 两侧的门；条件 $X \le R,\ R-1 \le Y$ 等价于房间 $R$ 落在区间所对应的房间范围内，允许 $X=R$ 的情况，即高桥站在房间 $R$ 即可操作门 $R$。）

如何取到最小的 $t$。 设 $x$、$y$ 分别为初始开着的门的最小、最大编号（下标从 $0$ 计）。所有初始开着的门最终都要被锁上，因此区间 $[X,Y]$ 必须覆盖 $[x,y]$，即 $X \le x$ 且 $Y \ge y$；再加上观察 3 的 $X \le R$、$Y \ge R-1$。为使区间最小（从而 $t$ 最小），取

$$X = \min(x, R), \qquad Y = \max(y, R-1).$$

换句话说：

• 若 $x \le R-1$，把区间左端取到 $x$（覆盖左侧所有开着的门）；否则左端取到 $R$；
• 若 $y \ge R$，把区间右端取到 $y$；否则右端取到 $R-1$。

于是 $t$ = 区间 $[X,Y]$ 内初始锁着、需要打开的门数，即

$$t = \big|\{i : X < i < R,\ L_i=1\}\big| + \big|\{i : R \le i < Y,\ L_i=1\}\big|,$$

其中端点 $x,y$ 本身是开着的门，不参与计数。

为什么正确。 一方面，任何解都必须覆盖所有初始开着的门且满足可达性条件，故开门集合至少不小于我们的最小区间，$t$ 不可能更小；另一方面，按上述区间执行"先全部打开、再逐一锁上"是可行的（区间始终包含房间 $R$ 附近的通道，高桥可从两端由外向里依次锁门），故 $\mathrm{open} + 2t$ 是可以达到的下界。答案即为 $\mathrm{open} + 2t$。

易错点：当没有任何开着的门时（全部初始已锁），$x,y$ 不存在，答案为 $0$，代码中用 $x=-1$ 特判；统计 $t$ 时只统计区间内部的锁着的门，不要误算端点的开着的门。

参考代码

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

int main() {
    int n, r;
    cin >> n >> r;
    vector<int> l(n);
    for (int i = 0; i < n; i++) cin >> l[i];

    int open = 0;
    for (int x : l) if (x == 0) open++;

    int x = -1, y = -1;
    for (int i = 0; i < n; i++) if (l[i] == 0) { x = i; break; }
    for (int i = n - 1; i >= 0; i--) if (l[i] == 0) { y = i; break; }

    int t = 0;
    if (x != -1) {
        if (x <= r - 1)              // 左边：区间 [x, r-1]
            for (int i = x + 1; i < r; i++) if (l[i] == 1) t++;
        if (y >= r)                  // 右边：区间 [r, y]
            for (int i = r; i < y; i++) if (l[i] == 1) t++;
    }
    cout << open + 2 * t << '\n';
    return 0;
}

复杂度分析

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

---

D - Long Waiting

题目链接：https://atcoder.jp/contests/abc423/tasks/abc423_d

题目大意

有一家最多同时容纳 $K$ 人的餐厅，门外一条队按到达顺序排队。今天有 $N$ 组顾客，第 $i$ 组有 $C_i$ 人，在时刻 $A_i$ 到达并排到队尾（$A_1 < A_2 < \cdots < A_N$），进入餐厅后停留 $B_i$ 个时间单位再离开。一组顾客只有在同时满足以下两个条件时才会进入餐厅：

• 该组此时位于队首；
• 该组人数与餐厅内现有顾客（包含恰在此时进入的、排除恰在此时离开的）人数之和不超过 $K$。

求每组进入餐厅的时刻。$N \le 3 \times 10^5$，$K \le 10^7$。

思路

这是典型的"排队 + 容量限制"模拟，用**优先队列（最小堆）**维护餐厅内顾客的离开时间。

算法流程。 依次处理第 $i$ 组，维护两个量：

• $t$：当前"队首时刻"（同时作为模拟时钟）；
• $\mathrm{sum}$：当前餐厅内人数。

第 $i$ 组到达队首的时刻是 $\max(t, A_i)$——它不可能早于前一组进入的时刻，也不可能早于自己到达的时刻。

若此时 $\mathrm{sum} + C_i \le K$，则第 $i$ 组在时刻 $\max(t, A_i)$ 直接进入。

否则空间不足，必须等有人离开。用最小堆（按离开时间排序）维护餐厅内各组的 $(离开时刻, 人数)$。不断弹出离开时刻最早的组：

$$t = \max(t, \text{该组离开时刻}), \qquad \mathrm{sum} \mathrel{-}= \text{该组人数},$$

直到 $\mathrm{sum} + C_i \le K$。此时第 $i$ 组进入，答案记为 $t$，并把 $(t + B_i, C_i)$ 压入堆，同时 $\mathrm{sum} \mathrel{+}= C_i$。

为什么正确。 最小堆保证每次都弹出"最该离开"（离开时刻最早）的那一组，因此 $t$ 的前进是最小步进；若被弹出的组离开时刻 $\le t$（本应早已离开），则 $t$ 不变，只把人数扣掉即可，这正好对应题目"排除恰在此时离开的顾客"的规则。由于组是按到达顺序依次进入（FIFO），前一组进入的时刻就是下一组到达队首的最早可能时刻，故队首时刻的计算也正确。整个过程不会把答案估早（$t$ 只会因实际离开而增大），也不会估晚（每次弹出的都是最早离开的组）。

注意：$t$ 可能累积到很大的值（最多约为 $\sum B_i + \max A_i$，数量级 $10^{12}$），要用 long long。

参考代码

#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;

    // 小根堆：(离开时刻, 人数)
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    vector<ll> ans;
    ll t = 0, sum = 0;

    for (ll i = 0; i < n; i++) {
        ll a, b, c;
        cin >> a >> b >> c;

        t = max(t, a);                 // 到达队首的时刻
        while (sum + c > k) {          // 空间不足，逐组让最早离开者先走
            auto [leave, cnt] = pq.top();
            pq.pop();
            t = max(t, leave);
            sum -= cnt;
        }

        ans.push_back(t);
        pq.push({t + b, c});
        sum += c;
    }

    for (ll v : ans) cout << v << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(N \log N)$（每组至多入堆、出堆各一次）
• 空间复杂度：$O(N)$

---

E - Sum of Subarrays

题目链接：https://atcoder.jp/contests/abc423/tasks/abc423_e

题目大意

给定长度为 $N$ 的整数序列 $A=(A_1,\ldots,A_N)$，有 $Q$ 次查询。每次给出 $L, R$，求

$$\sum_{l=L}^{R}\sum_{r=l}^{R}\sum_{j=l}^{r} A_j.$$

$N, Q \le 3 \times 10^5$，$1 \le A_i \le 100$。

思路

暴力是 $O(N^3)$ 级别，无法接受。核心技巧是换贡献视角：数一数每个 $A_j$ 被加了多少次。

$A_j$ 在某个三重和中被计入，当且仅当 $l \le j \le r$。因此 $A_j$ 的贡献次数等于满足

$$L \le l \le j \le r \le R$$

的整数对 $(l, r)$ 的个数：

• 满足 $L \le l \le j$ 的 $l$ 有 $j - L + 1$ 个；
• 满足 $j \le r \le R$ 的 $r$ 有 $R - j + 1$ 个。

两者相互独立，所以 $A_j$ 共被累加 $(j - L + 1)(R - j + 1)$ 次，答案为

$$\sum_{j=L}^{R} (j - L + 1)(R - j + 1)\, A_j.$$

把它展开：

$$(j - L + 1)(R - j + 1) = -j^2 + (L + R)\,j + (1 - L)(R + 1).$$

（验证：$(j + 1 - L)\big((R + 1) - j\big) = j(R+1) - j^2 + (1-L)(R+1) - (1-L)j = -j^2 + (L+R)j + (1-L)(R+1)$。）

于是

$$\text{答案} = -\sum_{j=L}^{R} j^2 A_j + (L+R)\sum_{j=L}^{R} j A_j + (1-L)(R+1)\sum_{j=L}^{R} A_j.$$

预处理三个前缀和（下标从 $1$ 开始）：

$$P_0[i] = \sum_{j=1}^{i} A_j, \qquad P_1[i] = \sum_{j=1}^{i} j A_j, \qquad P_2[i] = \sum_{j=1}^{i} j^2 A_j,$$

每次查询用区间和公式（$P_*[R] - P_*[L-1]$）$O(1)$ 求出三个和，再代入上式即可。

数值范围：$A_i \le 100$，最坏情况整个区间 $[L,R]$ 覆盖全数组时，答案约 $\sum_{子区间} (\text{长度}) \cdot 100 \approx 100 \cdot \frac{N^3}{6} \approx 4.5 \times 10^{17}$，在 64 位整数范围内，用 long long 足够。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, q;
    cin >> n >> q;

    vector<ll> p0(n + 1, 0), p1(n + 1, 0), p2(n + 1, 0);
    for (ll i = 1; i <= n; i++) {
        ll a;
        cin >> a;
        p0[i] = p0[i - 1] + a;
        p1[i] = p1[i - 1] + i * a;
        p2[i] = p2[i - 1] + i * i * a;
    }

    while (q--) {
        ll L, R;
        cin >> L >> R;
        ll s0 = p0[R] - p0[L - 1];
        ll s1 = p1[R] - p1[L - 1];
        ll s2 = p2[R] - p2[L - 1];
        ll ans = -s2 + (L + R) * s1 + (1 - L) * (R + 1) * s0;
        cout << ans << '\n';
    }
    return 0;
}

复杂度分析

• 时间复杂度：预处理 $O(N)$，每次查询 $O(1)$，总 $O(N + Q)$
• 空间复杂度：$O(N)$

---

F - Loud Cicada

题目链接：https://atcoder.jp/contests/abc423/tasks/abc423_f

题目大意

AtCoder 岛上有 $N$ 种蝉，第 $i$ 种蝉只在 $A_i$ 的倍数年份大爆发。在 $1$ 到 $Y$ 年中，求恰好有 $M$ 种蝉大爆发的年份数。$1 \le M \le N \le 20$，$Y, A_i \le 10^{18}$。

思路

$N \le 20$ 强烈提示枚举子集。记"条件 $i$"为"年份是 $A_i$ 的倍数"。

对每个子集 $S \subseteq \{1,\ldots,N\}$，定义两个量：

• 恰好条件 $f[S]$：满足 $S$ 中所有条件、且 $S$ 之外的所有条件都不满足的年份数；
• 部分条件 $g[T]$：满足 $T$ 中所有条件、其余条件任意满足或不满足的年份数。

部分条件很容易计算：$T$ 中条件全部满足等价于年份是 $\mathrm{lcm}(A_i : i \in T)$ 的倍数，故

$$g[T] = \left\lfloor \frac{Y}{\mathrm{lcm}(A_i : i \in T)} \right\rfloor.$$

两者满足关系：

$$g[T] = \sum_{S \supseteq T} f[S]$$

（左边统计的是"$T$ 全满足"，右边按"恰好满足的超集 $S$"分类求和）。

由 $g$ 反解 $f$（高维后缀差分类的 Möbius 变换）。 对每一位 $bi$，对所有不包含 $bi$ 的子集 $b$ 执行

$$g[b] \mathrel{-}= g[b \cup \{bi\}],$$

把 $N$ 位全部处理完后，$g[b]$ 就变成了恰好条件计数 $f[b]$。验证：变换本质上是 $f[T] = \sum_{S \supseteq T} (-1)^{|S| - |T|} g[S]$ 的迭代实现。

最终答案即为

$$\sum_{|S| = M} f[S].$$

溢出处理。 $\mathrm{lcm}$ 可能远超 $10^{18}$（甚至爆 64 位）。当它超过 $Y$ 时 $\lfloor Y / \mathrm{lcm} \rfloor = 0$，无需精确值。计算时维护 $prod = \mathrm{lcm}$，逐个并入 $A_j$：先算 $g = \gcd(prod, A_j)$，若 $\dfrac{prod}{g} > \left\lfloor \dfrac{Y}{A_j} \right\rfloor$，则令 $prod = Y + 1$ 并跳出；否则 $prod = \dfrac{prod}{g} \cdot A_j$。这样全程用除法判断，避免乘法溢出。

复杂度：$2^{20} \approx 10^6$ 个子集，每个子集 $O(N)$ 计算，加上变换 $O(N \cdot 2^N)$，完全可以接受。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m, y;
    cin >> n >> m >> y;
    vector<ll> a(n);
    for (ll i = 0; i < n; i++) cin >> a[i];

    int SZ = 1 << n;
    vector<ll> zeta(SZ, 0);

    // g[T] = floor(Y / lcm(A_i for i in T))
    for (ll b = 0; b < (1LL << n); b++) {
        ll prod = 1;
        for (ll j = 0; j < n; j++) {
            if (b & (1LL << j)) {
                ll g = gcd(prod, a[j]);
                if (prod / g > y / a[j]) {   // 防溢出：lcm 已超 Y
                    prod = y + 1;
                    break;
                }
                prod = prod / g * a[j];
            }
        }
        zeta[b] = y / prod;
    }

    // 高维后缀差分（Möbius 变换）：部分条件 -> 恰好条件
    for (ll bi = 0; bi < n; bi++) {
        for (ll b = 0; b < (1LL << n); b++) {
            if (!(b & (1LL << bi))) {
                zeta[b] -= zeta[b | (1LL << bi)];
            }
        }
    }

    // 按恰好满足的条件数统计
    vector<ll> cnt(n + 1, 0);
    for (ll b = 0; b < (1LL << n); b++) {
        cnt[__builtin_popcountll(b)] += zeta[b];
    }

    cout << cnt[m] << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(N \cdot 2^N)$
• 空间复杂度：$O(2^N)$

---

G - Small Multiple 2

题目链接：https://atcoder.jp/contests/abc423/tasks/abc423_g

题目大意

$T$ 组数据。每组给出整数 $K$ 与数字串 $S$（首位非 0），求最小的正整数 $n$，使得 $n$ 是 $K$ 的倍数，且 $n$ 的十进制表示中包含 $S$ 作为子串。$K \le 10^9$，$\sum |S| \le 5 \times 10^5$。答案可能超过 64 位整数范围，需以字符串形式输出。

思路

这是本场最难的题，核心是"把答案的形状固定下来后枚举"。记 $d$ 为 $K$ 的十进制位数，并记 $S \dot{+} T$ 为字符串拼接。

关键观察 1：答案至多有 $|S| + d$ 位。 考虑形如 $S \dot{+}$（$d$ 位）的整数：$S \cdot 10^d$ 到 $S \cdot 10^d + (10^d - 1)$ 是一段长度为 $10^d$ 的连续整数，而 $10^d > K$，任意连续 $K$ 个整数中必有 $K$ 的倍数，因此这段区间内必存在一个包含 $S$ 的 $K$ 的倍数。

于是可以把答案写成

$$n = t_{\mathrm{upper}} \dot{+} S \dot{+} t_{\mathrm{lower}},$$

其中 $t_{\mathrm{upper}}$、$t_{\mathrm{lower}}$ 为数字串（$t_{\mathrm{upper}}$ 允许前导零，实际数值不变），且

$$|t_{\mathrm{upper}}| + |t_{\mathrm{lower}}| \le d.$$

枚举分配。 对 $j = |t_{\mathrm{upper}}|$、$i = |t_{\mathrm{lower}}|$，枚举 $j + i = d$ 的 $d + 1$ 种分配 $(0,d), (1,d-1), \ldots, (d,0)$，对每种分配求出"该形状下数值最小的可行候选"，最后按数值大小取全局最小。对整数的字符串表示，先比位数、位数相同再比字典序即等价于比数值，这正是实现时的比较方式。

数学建模。 设 $c$ 为 $t_{\mathrm{upper}}$ 的数值（$0 \le c < 10^j$），$x$ 为 $t_{\mathrm{lower}}$ 的数值（$0 \le x < 10^i$，可前导补零）。则候选数的数值为

$$n = c \cdot 10^{|S| + i} + \mathrm{val}(S) \cdot 10^i + x.$$

令

$$h = 10^{|S|+i} \bmod K, \qquad \mathrm{base} = (\mathrm{val}(S) \bmod K) \cdot 10^i \bmod K,$$

则"$n$ 是 $K$ 的倍数"等价于同余方程

$$c \cdot h + \mathrm{base} + x \equiv 0 \pmod K.$$

对两种分配分别处理（选枚举量少的一侧，次数约为 $10^{\min(i,j)} \le 10^{\lfloor d/2 \rfloor}$）：

情形 1：$i \le j$（低位位数不多，枚举低位）。 枚举 $x = 0, 1, \ldots, 10^i - 1$。设 $g = \gcd(h, K)$。方程有解当且仅当 $\mathrm{base} + x$ 能被 $g$ 整除；此时令 $h' = h/g$，$K' = K/g$，由于 $\gcd(h', K') = 1$，方程的解为

$$c \equiv -\frac{\mathrm{base} + x}{g} \cdot (h')^{-1} \pmod{K'},$$

其中 $(h')^{-1}$ 是 $h'$ 模 $K'$ 的逆元。用 Euler 定理求逆：$\gcd(h', K') = 1$ 时 $h'^{\varphi(K')} \equiv 1 \pmod{K'}$，故 $(h')^{-1} \equiv h'^{\varphi(K')-1} \pmod{K'}$。取 $c$ 为 $[0, K')$ 中的最小非负解。对每个 $x$ 得到一个 $(c, x)$，取字典序最小者作为该分配的最优候选（因为固定 $i$ 时先最小化 $c$ 再最小化 $x$ 即最小化 $n$）。

情形 2：$i > j$（高位位数不多，枚举高位）。 从小到大枚举 $c = 0, 1, \ldots, 10^j - 1$。此时使 $n \equiv 0$ 的 $x$ 由方程唯一确定：

$$x = \big(K - (c \cdot h + \mathrm{base}) \bmod K\big) \bmod K,$$

只需检查 $x < 10^i$（能表示成至多 $i$ 位）。第一个可行的 $c$ 即该分配下的最小候选，直接取用并结束枚举。

比较与选取。 每个分配得到一个候选字符串：$(c = 0\ \text{时为空串，否则为 } c \text{ 的十进制串}) + S + (x \text{ 补齐为 } i \text{ 位})$。按 $(长度, 字典序)$ 比较取全局最小即可。

正确性。 对任意一个合法解（$n$ 包含 $S$，扩展位数 $\le d$），把 $S$ 前的部分记为 $t_{\mathrm{upper}}$、$S$ 后的部分记为 $t_{\mathrm{lower}}$，将其嵌入某个 $j + i = d$ 的分配（高位一侧补前导零不改变数值），情形 1/2 的枚举一定能找到数值不超过该合法解的候选；因此"所有分配中取最小"得到的必是全局最小。

实现细节。 乘法可能溢出（如 $c \cdot h$ 最大约 $10^{10} \times 10^9$），用 __int128 进行模乘；$\varphi(K/g)$ 通过对 $K/g$ 分解质因数计算；$K = 1$ 时 $\varphi(1) = 1$ 等边界也能被公式自然处理（此时任意数都是倍数，最小答案就是 $S$ 本身）。

参考代码

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

ll bpow(ll a, ll e, ll mod) {
    a %= mod;
    ll r = 1;
    while (e) {
        if (e & 1) r = (__int128)r * a % mod;
        a = (__int128)a * a % mod;
        e >>= 1;
    }
    return r % mod;
}

ll phi_of(ll x) {                       // 欧拉函数
    ll res = x;
    for (ll p = 2; p * p <= x; p++) {
        if (x % p == 0) {
            while (x % p == 0) x /= p;
            res = res / p * (p - 1);
        }
    }
    if (x > 1) res = res / x * (x - 1);
    return res;
}

string pad(ll x, int w) {               // 补零到 w 位
    if (w == 0) return "";
    string s = to_string(x);
    return string(w - (int)s.size(), '0') + s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        ll K; string S;
        cin >> K >> S;
        int lenS = (int)S.size();

        int d = 0;                       // K 的十进制位数
        for (ll t = K; t; t /= 10) d++;

        ll smodk = 0;                    // val(S) mod K
        for (char ch : S) smodk = (smodk * 10 + (ch - '0')) % K;

        vector<ll> p10(d + 1);           // 10^i, i <= d（K <= 1e9，d <= 10）
        p10[0] = 1;
        for (int i = 1; i <= d; i++) p10[i] = p10[i - 1] * 10;

        string ans = "";
        for (int i = 0; i <= d; i++) {   // i = |t_lower|, j = |t_upper|
            int j = d - i;
            ll h = bpow(10, lenS + i, K);                       // 10^{|S|+i} mod K
            ll base = (__int128)smodk * bpow(10, i, K) % K;
            ll g = gcd(h, K);
            ll Kp = K / g, hp = h / g;
            ll phi = phi_of(Kp);

            ll cbest = -1, xbest = -1;
            if (i <= j) {
                // 情形 1：枚举低位 x
                for (ll x = 0; x < p10[i]; x++) {
                    ll b = base + x;
                    if (b % g != 0) continue;
                    ll c = (Kp - (b / g) % Kp) % Kp;                    // (-b/g) mod K'
                    c = (__int128)c * bpow(hp, phi - 1, Kp) % Kp;       // 乘 (h')^{-1}
                    if (cbest == -1 || make_pair(c, x) < make_pair(cbest, xbest)) {
                        cbest = c; xbest = x;
                    }
                }
            } else {
                // 情形 2：枚举高位 c
                for (ll c = 0; c < p10[j]; c++) {
                    ll x = (K - (ll)(((__int128)c * h + base) % K)) % K;
                    if (x >= p10[i]) continue;
                    cbest = c; xbest = x;
                    break;
                }
            }

            if (cbest != -1) {
                string cand = (cbest == 0 ? "" : to_string(cbest)) + S + pad(xbest, i);
                if (ans == "" || make_pair(cand.size(), cand) < make_pair(ans.size(), ans)) {
                    ans = cand;
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

复杂度分析

• 时间复杂度：预计算 $\mathrm{val}(S) \bmod K$ 为 $O(|S|)$；对每种分配（共 $d+1$ 种）枚举至多 $10^{\min(i,j)} \le 10^{\lfloor d/2 \rfloor}$ 个值，每个值做一次 $O(\log K)$ 的模幂，故每数据约 $O(|S| + d \cdot 10^{\lfloor d/2 \rfloor} \log K)$。由于 $K \le 10^9$ 有 $d \le 10$，$10^{\lfloor d/2 \rfloor} \le 10^5$，在 $\sum |S| \le 5 \times 10^5$ 的限制下足够快。
• 空间复杂度：$O(d)$