[语言月赛 202409] 数字的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求求出满足「各位数字之和对 $p$ ~p~ 取模的余数最小」、且在该前提下数值最小的 $n$ ~n~ 位数。核心解法是按 $9n$ ~9n~ 与 $p$ ~p~ 的大小关系确定目标位和，再从左到右逐位贪心构造出最小的 $n$ ~n~ 位数。

分析

核心观察

一个 $n$ ~n~ 位数的各位数字之和可以取遍 $1 \sim 9n$ ~1 \sim 9n~ 中的每一个值，位和越小、取模后得到的余数就越小。能否让余数取到最小值 $0$ ~0~，取决于最大位和 $9n$ ~9n~ 与 $p$ ~p~ 的大小关系： $9n < p$ ~9n < p~ 时任何位和都小于 $p$ ~p~，余数等于位和本身，最小只能取 $1$ ~1~； $9n \ge p$ ~9n \ge p~ 时位和取 $p$ ~p~ 就能让余数为 $0$ ~0~，这也是可能的最小余数。

思路

由核心观察，最小余数只有两种可能，对应的目标位和也随之确定： $9n < p$ ~9n < p~ 时目标位和为 $1$ ~1~，否则目标位和为 $p$ ~p~。目标位和确定后，问题化归为「给定 $n$ ~n~ 与 $s$ ~s~，求位和恰为 $s$ ~s~ 的最小 $n$ ~n~ 位数」。

先说明 $9n \ge p$ ~9n \ge p~ 时为什么取位和 $p$ ~p~ 而不是更大的 $p$ ~p~ 的倍数。记 $f(s)$ ~f(s)~ 为位和恰为 $s$ ~s~ 的最小 $n$ ~n~ 位数。对 $s \ge 1$ ~s \ge 1~，把 $f(s+1)$ ~f(s+1)~ 中最靠右的非零位减 $1$ ~1~：若最高位是唯一的非零位，位和只能是 $1$ ~1~，与位和 $s + 1 \ge 2$ ~s + 1 \ge 2~ 矛盾，因此被减的这一位不是最高位，最高位不会被减成 $0$ ~0~。于是得到的仍是一个位和为 $s$ ~s~ 的合法 $n$ ~n~ 位数，且比 $f(s+1)$ ~f(s+1)~ 小，说明 $f(s) < f(s+1)$ ~f(s) < f(s+1)~。即 $f$ ~f~ 关于 $s$ ~s~ 严格递增，位和越小的候选数一定越小，所以在可以取到余数 $0$ ~0~ 的位和中取最小的那个，即 $p$ ~p~。同理， $9n < p$ ~9n < p~ 时余数等于位和，最小余数 $1$ ~1~ 对应位和 $1$ ~1~，此时最小的数就是 $f(1) = 10^{n-1}$ ~f(1) = 10^{n-1}~。

再逐位构造 $f(s)$ ~f(s)~。从左到右处理第 $i$ ~i~ 位（ $i = 0, 1, \dots, n - 1$ ~i = 0, 1, \dots, n - 1~），设已经用掉的位和为 $\text{used}$ ~\text{used}~，剩余位和 $r = s - \text{used}$ ~r = s - \text{used}~，当前位后面还剩 $m = n - 1 - i$ ~m = n - 1 - i~ 位，它们至多贡献 $9m$ ~9m~ 的位和。当前位要尽量小，但不能小到让后面的位塞不下剩余位和，于是

$\displaystyle d_i = \max\left( \text{lo},\ r - 9m \right),\qquad \text{lo} = \begin{cases} 1, & i = 0 \\ 0, & i > 0 \end{cases}$

下界 $\text{lo}$ ~\text{lo}~ 保证最高位不为 $0$ ~0~；若 $r - 9m$ ~r - 9m~ 更小说明后面装得下，当前位可以取到下界 $\text{lo}$ ~\text{lo}~。取完当前位后剩余位和变为 $r - d_i \le 9m$ ~r - d_i \le 9m~，恰好能被后面的 $m$ ~m~ 位装满，因此构造过程不会中途失败。每一位都取了「保证后面还能补齐」前提下的最小值，逐步比较即知结果正是 $f(s)$ ~f(s)~。

朴素做法是枚举全部 $n$ ~n~ 位数，计算位和后打擂台，复杂度 $O(10^n \cdot n)$ ~O(10^n \cdot n)~；本题 $n \le 7$ ~n \le 7~ 时该做法也能通过，但上面的贪心只需 $O(n)$ ~O(n)~，且不依赖 $n$ ~n~ 的具体范围。

具体示例

以样例 #1（ $n = 3$ ~n = 3~， $p = 8$ ~p = 8~）为例。 $9n = 27 \ge 8$ ~9n = 27 \ge 8~，目标位和取 $8$ ~8~。第 $1$ ~1~ 位后面还剩 $2$ ~2~ 位，至多贡献 $18$ ~18~，故 $d_0 = \max(1, 8 - 18) = 1$ ~d_0 = \max(1, 8 - 18) = 1~，剩余位和变为 $7$ ~7~；第 $2$ ~2~ 位后面还剩 $1$ ~1~ 位，至多贡献 $9$ ~9~，故 $d_1 = \max(0, 7 - 9) = 0$ ~d_1 = \max(0, 7 - 9) = 0~，剩余位和仍为 $7$ ~7~；第 $3$ ~3~ 位之后没有位了， $d_2 = 7$ ~d_2 = 7~。得到 $107$ ~107~，位和 $1 + 0 + 7 = 8$ ~1 + 0 + 7 = 8~，余数 $0$ ~0~，与样例一致。

样例 #3（ $n = 5$ ~n = 5~， $p = 3$ ~p = 3~）同理： $9n = 45 \ge 3$ ~9n = 45 \ge 3~，目标位和取 $3$ ~3~，第 $1$ ~1~ 位只能取 $1$ ~1~（最高位不为 $0$ ~0~），此后剩余位和 $2$ ~2~ 小于后面各位置的上界，中间各位都取 $0$ ~0~，最后一位取 $2$ ~2~，得到 $10002$ ~10002~。

样例 #4（ $n = 2$ ~n = 2~， $p = 7$ ~p = 7~）： $9n = 18 \ge 7$ ~9n = 18 \ge 7~，目标位和取 $7$ ~7~，第 $1$ ~1~ 位取 $\max(1, 7 - 9) = 1$ ~\max(1, 7 - 9) = 1~，第 $2$ ~2~ 位取 $6$ ~6~，得到 $16$ ~16~。

另一分支的例子： $n = 7$ ~n = 7~、 $p = 100$ ~p = 100~ 时 $9n = 63 < 100$ ~9n = 63 < 100~，任何 $7$ ~7~ 位数的位和都小于 $100$ ~100~，余数等于位和，最小余数 $1$ ~1~ 由位和最小的 $10^{6} = 1000000$ ~10^{6} = 1000000~ 取到。

算法步骤

读入 n 与 p。
若 $9 \times$ ~9 \times~ n 小于 p，最小余数只能取 $1$ ~1~，答案固定为 1 后面跟 n - 1 个 0，即 $10^{n-1}$ ~10^{n-1}~，输出后结束。
否则令剩余位和 rest 等于 p，并准备一个空字符串存放答案。
从左到右枚举第 i 位（ $i = 0, 1, \dots, n - 1$ ~i = 0, 1, \dots, n - 1~）：令后面剩余位数 remaining 为 n - 1 - i，令下界 low 在 $i = 0$ ~i = 0~ 时取 $1$ ~1~、其余情况取 $0$ ~0~，再令当前位 d 取 low 与 rest - 9 * remaining 中的较大者。
把 d 追加到答案字符串，并令 rest 减去 d。
输出答案字符串。

复杂度分析

时间：只需从左到右构造 $n$ ~n~ 位数字，为 $O(n)$ ~O(n)~。
空间：答案字符串占 $O(n)$ ~O(n)~，不计输入输出。

实现注意事项

最高位不能为 $0$ ~0~：构造第 $1$ ~1~ 位时下界是 $1$ ~1~，其余位的下界是 $0$ ~0~。样例 #2（ $n = 1$ ~n = 1~， $p = 1$ ~p = 1~）的答案是 $1$ ~1~ 而不是 $0$ ~0~，因为 $0$ ~0~ 不是 $1$ ~1~ 位数。
分类的判据是 $9n$ ~9n~ 与 $p$ ~p~ 的大小关系： $9n < p$ ~9n < p~ 时余数不可能为 $0$ ~0~，目标位和是 $1$ ~1~ 而非 $p$ ~p~； $9n \ge p$ ~9n \ge p~ 时位和 $p$ ~p~ 一定可达，目标位和才是 $p$ ~p~。样例 #2 的 $p = 1$ ~p = 1~ 也落在后一分支，目标位和 $1$ ~1~ 与 $p$ ~p~ 恰好相等。
目标位和不能取更小的值： $9n \ge p$ ~9n \ge p~ 时位和 $0$ ~0~ 不可能出现（ $n$ ~n~ 位数的位和至少为 $1$ ~1~），而 $p$ ~p~ 是不超过 $9n$ ~9n~ 的最小正倍数。
逐位取值时 $9 \times$ ~9 \times~ 剩余位数的上界不可缺少：没有它就会构造出后半段装不下的数字串，位和达不到目标值。
边界 $9n = p$ ~9n = p~ 落在 $9n \ge p$ ~9n \ge p~ 分支，目标位和 $p = 9n$ ~p = 9n~，每一位都取 $9$ ~9~（例如 $n = 7$ ~n = 7~、 $p = 63$ ~p = 63~ 时答案为 $9999999$ ~9999999~）。
答案用字符串逐位拼接，不必计算 $10^{n-1}$ ~10^{n-1}~ 这样的幂，也就避免了整型溢出问题；n = 1 时分支一的答案就是 1。
输入只有一行两个整数，Python 中直接 split() 读取即可。

源代码

#include <iostream>
#include <string>

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

    int n = 0, p = 0;
    if (!(std::cin >> n >> p)) return 0;

    if (9 * n < p) {
        // 各位数字之和最大为 9n，永远达不到 p，最小余数由最小位和 1 取得
        std::cout << '1' << std::string(n - 1, '0') << '\n';
        return 0;
    }

    // 余数 0 可以达到，位和取最小的正倍数 p，再逐位构造最小的那个数
    int rest = p;
    std::string answer;
    for (int i = 0; i < n; ++i) {
        const int remaining = n - 1 - i;      // 当前位之后还剩几位
        const int low = (i == 0) ? 1 : 0;     // 最高位不能为 0
        int d = rest - 9 * remaining;         // 后面塞不下的部分必须由当前位承担
        if (d < low) d = low;
        answer += static_cast<char>('0' + d);
        rest -= d;
    }
    std::cout << answer << '\n';
    return 0;
}

import sys


def main():
    n, p = map(int, sys.stdin.read().split()[:2])

    if 9 * n < p:
        # 各位数字之和最大为 9n，永远达不到 p，最小余数由最小位和 1 取得
        sys.stdout.write("1" + "0" * (n - 1) + "\n")
        return

    # 余数 0 可以达到，位和取最小的正倍数 p，再逐位构造最小的那个数
    rest = p
    digits = []
    for i in range(n):
        remaining = n - 1 - i          # 当前位之后还剩几位
        low = 1 if i == 0 else 0       # 最高位不能为 0
        d = max(low, rest - 9 * remaining)  # 后面塞不下的部分必须由当前位承担
        digits.append(str(d))
        rest -= d
    sys.stdout.write("".join(digits) + "\n")


if __name__ == "__main__":
    main()

目前没有评论。