digits 2 - 题解

标签与难度

标签: 构造, 数论, 模运算, 数学, GCD 难度: 1200

题目大意喵~

主人你好，喵~ 这是一道有趣的构造题哦！

题目会给我们一个正整数 $n$ (其中 $1 \le n \le 100$ )。我们的任务是找到另一个正整数，我们叫它 $M$ 好了，这个 $M$ 必须同时满足下面三个条件呐：

$M$ 的所有位数加起来的总和，必须能被 $n$ 整除。
$M$ 本身的值，也必须能被 $n$ 整除。
$M$ 的位数不能超过 $10^4$ 位。

如果能找到这样的数，就把它打印出来。如果有很多个答案，随便打印一个就好啦。如果找不到，就输出 "Impossible"。

举个栗子，如果 $n=3$ ，一个可能的答案是 $333$ 。因为它的各位数之和是 $3+3+3=9$ ，可以被 $3$ 整除。而且 $333$ 本身也能被 $3$ 整除。完美，喵！

解题思路分析

这道题要求我们去“构造”一个满足条件的数字，而不是去一个个地暴力搜索，因为数字可能非常大呀，喵~

那我们怎么来构造这个神奇的数字 $M$ 呢？

一个很自然的想法是，用给定的 $n$ 本身作为“积木”来搭建我们的 $M$ 。比如说，如果 $n=12$ ，我们可以尝试用 "12" 来构造 $M$ ，比如 $M$ 可以是 $12$ 、 $1212$ 、 $121212$ …… 这样拼接起来。

让我们看看这种构造方法有什么好处，喵~

假设我们把数字 $n$ 的字符串形式重复 $k$ 次，得到新的数字 $M$ 。

1. 先看条件二： $M$ 能否被 $n$ 整除？

答案是：一定可以的！为什么呢？让我们来分析一下。如果 $n=12$ ， $k=3$ ，那么 $M = 121212$ 。我们可以把它拆开看： $M = 120000 + 1200 + 12$ $M = 12 \times 10000 + 12 \times 100 + 12 \times 1$ $M = 12 \times (10000 + 100 + 1)$ 看吧！ $M$ 显然是 $12$ 的倍数。

推广到一般情况，如果数字 $n$ 有 $d$ 位，那么将 $n$ 重复 $k$ 次，得到的数字 $M$ 可以表示为：

M = n \cdot 10^{d(k-1)} + n \cdot 10^{d(k-2)} + \dots + n \cdot 10^d + n

M = n \cdot \sum_{i=0}^{k-1} 10^{di}

因为 $n$ 是 $M$ 的一个因子，所以 $M$ 一定能被 $n$ 整除！太棒了！只要我们用这种方法构造， $M$ 的值能被 $n$ 整除这个条件就自动满足了，我们完全不用再担心它了，喵~

2. 再看条件一： $M$ 的各位数之和能否被 $n$ 整除？

现在我们只需要专注于这一个条件了。设数字 $n$ 本身的各位数之和为 $s$ 。例如，如果 $n=12$ ，那么 $s = 1+2=3$ 。如果我们将 $n$ 重复 $k$ 次来构造 $M$ ，那么 $M$ 的各位数之和就是 $s$ 重复了 $k$ 次，也就是 $s \times k$ 。所以我们的问题就转化为了：找到一个正整数 $k$ ，使得 $(s \times k)$ 能够被 $n$ 整除。

怎么找到这个 $k$ 呢？最简单的办法，就是让 $k=n$ 。这样，各位数之和就是 $s \times n$ ，这当然能被 $n$ 整除了！这个方法一定能找到一个解，而且因为 $n \le 100$ ，重复 $n$ 次后的总位数最多是 $3 \times 100 = 300$ 位（当 $n=100$ 时），远小于 $10^4$ 的限制。所以这是一个绝对可行的简单解法。

但是，我们是追求完美的我，能不能找到一个最小的 $k$ 呢？当然可以！我们要找最小的正整数 $k$ ，使得 $s \times k$ 是 $n$ 的倍数。这其实是在要求 $s \times k$ 是 $s$ 和 $n$ 的公倍数。为了让 $k$ 最小，我们应该让 $s \times k$ 成为 $s$ 和 $n$ 的最小公倍数(lcm)。也就是说：

s \times k = \text{lcm}(s, n)

我们又知道一个超级有用的数论公式：

\text{lcm}(a, b) \times \gcd(a, b) = a \times b

其中 $\gcd(a,b)$ 是 $a$ 和 $b$ 的最大公约数。所以， $\text{lcm}(s, n) = \frac{s \times n}{\gcd(s, n)}$ 。

代入回去：

s \times k = \frac{s \times n}{\gcd(s, n)}

两边同时除以 $s$ （因为 $n$ 是正整数，所以 $s$ 也是正的），我们就得到了 $k$ 的值：

k = \frac{n}{\gcd(s, n)}

这就是我们需要的最小重复次数 $k$ 啦！

总结一下我们的完美策略：

读入 $n$ 。
计算出 $n$ 的各位数之和，记为 $s$ 。
计算 $k = \frac{n}{\gcd(s, n)}$ 。
将数字 $n$ 连续输出 $k$ 次。

这样构造出来的数字，一定满足所有条件，并且是这种构造方式下最短的解！而且因为我们已经证明了总能找到解，所以 "Impossible" 的情况是不会发生的哦。

代码实现

这是我根据上面的思路，精心为你准备的代码哦，喵~

cpp

#include <iostream>
#include <string>
#include <numeric> // C++17 标准库，提供了 std::gcd

// 一个帮助函数，用来计算一个数的各位数之和，喵~
int getDigitSum(int num) {
    int sum = 0;
    std::string s = std::to_string(num); // 转成字符串方便遍历每一位
    for (char c : s) {
        sum += c - '0'; // 把字符'0'-'9'转成数字0-9
    }
    return sum;
}

// 如果你用的不是C++17或更高版本，可以自己实现一个gcd函数
// int gcd(int a, int b) {
//     return b == 0 ? a : gcd(b, a % b);
// }

void solve() {
    int n;
    std::cin >> n;

    // 1. 计算 n 的各位数之和 s
    int digitSum = getDigitSum(n);

    // 2. 计算 n 和 s 的最大公约数
    // C++17 提供了 std::gcd，非常方便！
    int commonDivisor = std::gcd(n, digitSum);

    // 3. 根据我们的公式计算最小重复次数 k
    int numRepetitions = n / commonDivisor;

    // 4. 重复打印 n，一共 k 次
    for (int i = 0; i < numRepetitions; ++i) {
        std::cout << n;
    }
    std::cout << std::endl;
}

int main() {
    // 为了提高 cin 和 cout 的速度，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    // 题目可能包含多个测试用例，虽然样例里没有，但是参考代码中有，这是个好习惯
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

时间复杂度: $O(T \cdot n \log_{10} n)$ 对于每个测试用例（总共有 $T$ 个）：
1. getDigitSum(n): 将数字 $n$ 转为字符串，长度为 $O(\log_{10} n)$ ，遍历一次，所以是 $O(\log_{10} n)$ 。
2. std::gcd(n, digitSum): 计算最大公约数，复杂度大约是 $O(\log n)$ 。
3. 循环打印：循环次数 $k = n / \gcd(s, n)$ ，最坏情况下 $k=n$ 。每次打印数字 $n$ 需要 $O(\log_{10} n)$ 的时间。所以这部分是 $O(k \cdot \log_{10} n)$ ，也就是 $O(n \log_{10} n)$ 。因为 $n \le 100$ ，所以这个计算量非常小，跑起来飞快，喵~
空间复杂度: $O(\log_{10} n)$ 我们主要用了几个变量来存储 $n$ , digitSum, k 等，这些都是常数级的空间。getDigitSum 中 std::to_string 会临时创建一个字符串，其长度为 $O(\log_{10} n)$ 。所以空间复杂度非常低。

知识点总结

构造法: 面对求解问题，有时直接构造一个满足条件的解，比搜索解空间更有效。通过分析题目性质，找到一个必能成功的构造模式是关键。
问题简化: 通过“重复拼接 $n$ ” 的构造方式，我们巧妙地将两个条件简化为了一个。这是解题中非常重要的思想哦！
数论基础:
- 整除性: 理解整除的基本性质。
- 最大公约数 (GCD): GCD 在数论问题中是常客，是解决许多问题的钥匙。
- 最小公倍数 (LCM): 通过 lcm(a,b) * gcd(a,b) = a*b 这个公式，我们将问题从找 LCM 转化为了找 GCD，计算起来更方便。

希望这篇题解能帮到你，喵~ 如果还有不懂的地方，随时可以再来问我哦！一起加油，成为算法大师吧！

digits 2 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

1. 先看条件二：MMM 能否被 nnn 整除？ ​

2. 再看条件一：MMM 的各位数之和能否被 nnn 整除？ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​