自动搬运

查看原文

来自洛谷，原作者为

	szh_AK_all S挂分挂到被洛谷7级勾卡线|I can do all things

搬运于2025-08-24 21:16:39，当前版本为作者最后更新于2024-07-31 23:55:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Source & Knowledge

2024 年 9 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

求满足在各位数字之和对 $p$ 取模的值最小的最小 $n$ 位数。

解法 1

本题考察简单循环与分支的应用。

由于 $n$ 很小，所以可以枚举所有的 $n$ 位数，计算枚举到的数的各位数字对 $p$ 取模的值，通过打擂台的方法找出各位数字之和对 $p$ 取模的值最小的最小 $n$ 位数。

求各数位之和的代码如下：

int get(int x) {
    int sum = 0;
    while (x) {
        sum += x % 10;
        x /= 10;
    }
    return sum;
}

解法 2

当然，本题 $n,p$ 的范围也可以扩大，可以用贪心算法解决。

由于最终答案限定为 $n$ 位数，而 $n$ 位数的各位数字之和最大为 $n\times 9$（即每一位的数字都为 $9$）。那么可以将 $n\times 9$ 与 $p$ 的大小关系进行分类讨论，从而解决此题。

• $n\times 9<p$，则无论这个 $n$ 位数是多少，它的各位数字之和都不会达到 $p$，那么最终答案的各位数字之和对 $p$ 取模的值不会为 $0$，但可以为 $1$，所以最终答案的各位数字之和就是 $1$，$x$ 为 $10^{n-1}$。

• $n\times9\ge p$，此时，$n$ 位数的各位数字之和对 $p$ 取模的值可以为 $0$，而又因为答案要尽可能小，所以最终答案的各位数字之和应为 $p$。也就是说，要在保证答案的各位数字之和为 $p$ 的同时，我们还需要令答案尽可能小，也就是让它高位上的数字尽可能小。显然，答案的最高位是不能为 $0$ 的，而中间位是否为 $0$ 取决于剩下的还需拼凑的各位数字之和是否可以拼凑出来。