E. Novice's Mistake - 题解
比赛与标签
比赛: Codeforces Round 957 (Div. 3) 标签: brute force, constructive algorithms, implementation, math, strings 难度: *1700
题目大意喵~
这道题目讲了一个有趣的故事：有一个叫 K1o0n 的新手程序员，他本来想计算 n * a - b 的值。但是呢，他一不小心把 n 当作一个字符串来处理了，导致计算过程变得非常奇妙：
- 错误的乘法: 他把数字
n对应的字符串n_str重复了a次，拼接成一个长长的字符串s。比如n=2, a=3，他就得到了"222"。 - 错误的减法: 他从长字符串
s的末尾删掉了b个字符。
现在，题目要求我们找出，对于给定的 n，有多少对 (a, b)（在题目给定的范围内），能让 K1o0n 的错误代码得出正确的结果。所谓“正确的结果”，就是指他得到的非空字符串，在转换成数字后，恰好等于 n * a - b 的真实值。
输入:
t组测试数据。- 每组数据一个整数
n（1 <= n <= 100）。
输出:
- 首先输出满足条件的
(a, b)对的数量x。 - 接着
x行，每行输出一对a和b。
解题思路详解的说！
遇到这种看似复杂的字符串和数字混合的问题，咱们的第一步就是要把它转化成纯粹的数学关系式，这样才能看清问题的本质呐！
1. 建立数学模型
让咱们来定义几个变量，把问题描述清楚喵~
n_{int}: 整数n的值。n_str:n对应的字符串形式。k:n_str的长度，也就是k = length(to_string(n_{int}))。a,b: 题目中我们要找的两个整数。
K1o0n 的错误操作是：
- 字符串
s是n_str重复a次，所以s的长度是a * k。 - 从
s末尾去掉b个字符后得到新字符串s'，那么s'的长度就是L = a * k - b。 - 这个
s'必须非空，所以L >= 1。
正确的结果是：
- 正确的数值是
n_{int} * a - b。
题目要求错误操作的结果等于正确的结果，也就是说，字符串 s' 转换成的整数 X，要满足： X = n_{int} * a - b
现在我们有两个关于 b 的等式了：
- 从长度关系得出:
b = a * k - L - 从数值关系得出:
b = n_{int} * a - X
把这两个等式连起来，消去 b，就得到了最核心的关系式！ a * k - L = n_{int} * a - X
整理一下，把带 a 的项移到一边，其他的移到另一边： X - L = n_{int} * a - a * kX - L = a * (n_{int} - k)
为了方便书写，我们让 d = k - n_{int}。那么核心方程就变成了： X - L = a * (-d) 也就是 a * d = L - X
这里的 X 是字符串 s' 的整数值，而 s' 是由 n_str 不断重复形成的前缀，其长度为 L。
2. 分类讨论大法好！
现在我们有了核心方程 a * d = L - X，可以根据 d = k - n_{int} 的值来分情况讨论啦。 对于题目给定的 1 <= n <= 100：
- 如果
n = 1，k=1，则d = 1 - 1 = 0。 - 如果
2 <= n <= 9，k=1，则d = 1 - n < 0。 - 如果
10 <= n <= 99，k=2，则d = 2 - n < 0。 - 如果
n = 100，k=3，则d = 3 - 100 < 0。
所以 d 只可能等于0或小于0，代码里那个 d > 0 的分支在本次比赛的约束下是走不到的，不过我们还是分析一下所有情况喵。
情况一：d = 0 (只有 n = 1 时成立) 当 d = 0，我们的方程变成了 0 = L - X，也就是说 L = X。 一个数字的字符串长度要等于它本身的值，这太罕见啦！
L=1，X是一位数。X=1时，L=1。Bingo！s'必须是"1"。L=2，X是两位数。X最小是10，而L只有2，L=X不可能成立。L更大时就更不可能啦。
所以，当 n=1 时，最终得到的字符串 s' 必须是 "1"，它的值 X=1，长度 L=1。 我们把 X=1, L=1, n=1, k=1 代入 b 的计算公式： b = n * a - X = 1 * a - 1 = a - 1 我们需要找到满足约束的 a：
1 <= a <= 100001 <= b <= min(10000, n*a)=>1 <= a-1 <= min(10000, a)从1 <= a-1得到a >= 2。 所以a的取值范围是[2, 10000]。对于每一个这样的a，都有一个对应的b = a - 1，构成一个解。
情况二：d < 0 (当 n > 1 时成立) 这时，我们把方程 a * d = L - X 变形成： a * (-d) = X - L。 因为 d < 0，所以 -d > 0。我们令 abs_d = -d = n_{int} - k。 方程就是 a * abs_d = X - L。 于是 a = (X - L) / abs_d。
因为 a 必须是正整数，所以 (X - L) 必须是 abs_d 的正整数倍。 这里的 X 和 L 都是未知的，但它们是关联的：X 是由 n_str 生成的长度为 L 的前缀字符串的值。
我们直接去枚举 a 和 b 肯定会超时，那怎么办呢？ 注意到 a 有上限 10000，abs_d 是个定值。所以 X-L 也有上限。 X - L = a * abs_d <= 10000 * (n_{int} - k)。 X 的值大约是 10^(L-1)，它随 L 指数增长，而 L 本身是线性增长。所以 X 增长得比 L 快得多。 10^(L-1) 级别的值不能太大，这意味着 L 也不能太大。 我们可以估算一下，10000 * (100-3) = 970000。10^6 = 1,000,000。所以 L 大概不会超过 6 或 7。 这启发我们，可以去枚举最终结果的长度 L！L 的范围很小。
我们的策略就出来啦：
- 对于给定的
n > 1，计算出abs_d = n - k。 - 在一个小的范围内枚举
L（比如从1到7，这是一个安全的上界）。 - 对于每个
L，生成由n_str重复构成的长度为L的前缀字符串s'。 - 将
s'转换为整数X。 - 检查
(X - L)是否为正且能被abs_d整除。 - 如果可以，计算出
a = (X - L) / abs_d。 - 验证
a是否在[1, 10000]范围内。 - 如果
a合法，计算b = n * a - X。 - 验证
b是否在[1, min(10000, n*a)]范围内。 - 如果所有检查都通过，那么
(a, b)就是一个解！
这个方法通过枚举一个很小的量 L，巧妙地找到了所有可能的解，太棒了喵！
代码实现喵
// 完整的AC代码，添加详细注释解释关键逻辑
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// 这是一个辅助函数，用来生成由 n_str 重复拼接而成，长度为 L 的前缀字符串
// 比如 n_str="12", L=5, 它会返回 "12121"
string generate_prefix(string n_str, int L) {
string s = "";
while (static_cast<int>(s.length()) < L) {
s += n_str;
}
return s.substr(0, L);
}
int main() {
// 加速输入输出，是好习惯喵~
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
string n_str = to_string(n);
int k = n_str.length();
int d = k - n; // 我们推导出的关键先生 d
vector<pair<int, int>> results; // 用来存放找到的答案 (a, b)
if (d == 0) {
// 这是 n=1 的特殊情况
// 我们推导出 L=X=1, b = a-1
// a 的范围是 [2, 10000]
for (int a = 2; a <= 10000; a++) {
int b = n * a - 1; // n=1, X=1, 所以 b = a - 1
results.push_back(make_pair(a, b));
}
} else if (d > 0) {
// 对于 1 <= n <= 100, k 总是小于等于 n, 所以 d <= 0
// 这个分支在题目给定的约束下是执行不到的，喵~
// 不过代码的健壮性还是值得肯定的！
int max_a = min(10000, 6 / d);
for (int a = 1; a <= max_a; a++) {
int min_L = max(1, a * d + 1);
for (int L = min_L; L <= 7; L++) {
int X = L - a * d;
if (X < 1) continue;
string T_str = to_string(X);
if (static_cast<int>(T_str.length()) != L)
continue;
string prefix = generate_prefix(n_str, L);
if (prefix != T_str)
continue;
int b = n * a - X;
if (b < 1)
continue;
int max_b = min(10000, n * a);
if (b > max_b)
continue;
results.push_back(make_pair(a, b));
}
}
} else { // d < 0, 这是 n > 1 的情况
int abs_d = -d; // abs_d = n - k
// 我们枚举结果的长度 L，L不需要很大，7就足够了
for (int L = 1; L <= 7; L++) {
string prefix_str = generate_prefix(n_str, L);
try {
// 将前缀字符串转成数字 X
// 用 long long 来避免中间转换溢出，虽然这里 int 也够用
long long X_ll = stoll(prefix_str);
int X = X_ll;
// a = (X - L) / abs_d
// 检查 X-L 是否为正，以及是否能被 abs_d 整除
if (X <= L) continue;
if ((X - L) % abs_d != 0) continue;
int a = (X - L) / abs_d;
// 检查 a 的范围
if (a < 1 || a > 10000) continue;
// 计算 b
int b = n * a - X;
// 检查 b 的范围
if (b < 1) continue;
int max_b = min(10000, n * a);
if (b > max_b) continue;
// 找到了一对合格的 (a,b)，加入结果集！
results.push_back(make_pair(a, b));
} catch (...) {
// 如果 stoll/stoi 转换失败（比如字符串太长），就跳过
continue;
}
}
}
// 虽然题目没要求，但排序后输出是个好习惯
sort(results.begin(), results.end());
cout << results.size() << endl;
for (auto &p : results) {
cout << p.first << " " << p.second << endl;
}
}
return 0;
}复杂度分析
- 时间复杂度: O(t) 的说。 对于每组测试数据，主要的计算发生在
d < 0的情况。我们有一个L从1到7的循环，这是一个很小的常数。循环内部的操作，如生成前缀、字符串转数字等，其复杂度都与L和k相关，而L和k都很小。因此，处理每个测试用例的时间可以看作是常数时间。总时间复杂度就是测试数据组数t乘以一个常数，即O(t)。 - 空间复杂度: O(A_max) 的说。 空间主要用来存储结果。在
n=1的情况下，结果数量最多，大约是10000。对于n>1的情况，结果数量最多只有7个左右。所以空间复杂度取决于a的上限，即O(A_max)，在这里是O(10000)。
知识点与总结
这真是一道把人绕得晕乎乎，但想通了就豁然开朗的题目呢，喵！
- 问题转化: 解决这类问题的核心技巧，就是把复杂的、混合了不同数据类型（字符串、整数）的描述，转化为清晰的数学方程。
a * d = L - X这个方程就是我们解题的钥匙！ - 分类讨论: 根据关键变量
d = k - n的性质进行分类讨论，是让复杂问题变得条理清晰的经典方法。在这里，我们分成了d=0和d<0两种实际情况来处理。 - 枚举与剪枝: 当直接枚举解
(a, b)的范围过大时，要思考是否可以枚举一个范围更小的中间变量。本题中，我们放弃枚举a，转而枚举结果长度L，并通过分析L的取值范围非常有限，成功地将暴力搜索变成了一个高效的算法。这就是漂亮的剪枝思想！ - 边界与实现: 在实现时，要注意各种边界条件，比如
a和b的取值范围，以及字符串转数字可能存在的溢出问题（虽然本题数据范围下int足够，但使用long long过渡或者try-catch是更稳妥的编程习惯）。
希望这篇题解能帮助大家更好地理解这道题！只要我们静下心来，一步步分析，再复杂的问题也能被我们优雅地解决掉的！大家继续加油哦，喵~ >w<