数字题解

szh_AK_all · 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 的大小关系进行分类讨论，从而解决此题。