【CSP】CSP-X 2018真题 | 11的倍数 luogu-B4075 （适合GESP三级及以上考生练习）
CSP-X 2018真题-11的倍数，一道结合字符串处理与数学整除性判定的题目，考察对大整数的按位处理以及模运算的应用。由于数据位数可达100位，需要用字符串代替整型变量来处理输入。适合GESP三级及以上考生练习，难度⭐⭐。
B4075 [CSP-X 2018] 11 的倍数
题目要求
题目描述
如何判断一个正整数 $x$ 是不是 $3$ 的倍数？
可以计算 $x\div3$ 所得的余数，如果余数等于 $0$，那么 $x$ 是 $3$ 的倍数。
还可以用下面的方法来判断：
把 $x$ 的个位数字、十位数字、百位数字……相加，如果所得的和是 $3$ 的倍数，那么 $x$ 就是 $3$ 的倍数。例如：$x = 8511$，$8+5+1+1=15$，$15$ 是 $3$ 的倍数，那么 $8511$ 就是 $3$ 的倍数。
接下来你的任务是，判断 $x$ 是不是 $11$ 的倍数。
有一个与判断是不是 $3$ 的倍数类似的方法供你参考：
- 把 $x$ 的个位、百位、万位……上的数字求和，得 $s_1$；
- 把 $x$ 的十位、千位、十万位……上的数字求和，得 $s_2$；
如果 $s_1\div11$ 所得的余数 $= s_2\div11$ 所得的余数，那么 $x$ 就是 $11$ 的倍数。
例如：$x=3162819$，$s_1 = 3+6+8+9 = 26$，$s_2 = 1+2+1 = 4$。因为 $26\div11$ 余 $4$，$4\div11$ 也余 $4$，所以 $3162819$ 是 $11$ 的倍数。
输入格式
第一行，一个正整数 $n$。
以下 $n$ 行，每行一个正整数 $x_i$，需要你判断 $x_i$ 是不是 $11$ 的倍数。
输出格式
$n$ 行，每行输出一个 $\texttt{Yes}$ 或 $\texttt{No}$，表示 $x_i$ 是不是 $11$ 的倍数。
输入输出样例 #1
输入 #1
1
2
3
4
3
2035
62202
335
输出 #1
1
2
3
Yes
No
No
说明/提示
对于 $30\%$ 的数据，$x_i$ 的位数不超过 $9$ 位；
对于 $50\%$ 的数据，$x_i$ 的位数不超过 $17$ 位；
对于 $100\%$ 的数据，$x_i$ 的位数不超过 $100$ 位，$n$ 不超过 $10$。
题目分析
本题考察的核心是11 的整除性判定法则以及大整数的字符串处理。由于输入数字最多可达 100 位，远超 long long 的表示范围（约 18 位），因此必须以字符串形式读入并逐字符处理。
解题思路分析：
- 理解判定规则：
- 从个位（最右边）开始，按位置的奇偶性将数字分为两组：个位、百位、万位……求和得 $s_1$；十位、千位、十万位……求和得 $s_2$。
- 若 $s_1 \mod 11 = s_2 \mod 11$，则 $x$ 是 $11$ 的倍数。
- 这本质上等价于判断 $s_1 - s_2$ 是否为 $11$ 的倍数（即奇偶位数字交替和能被 $11$ 整除）。
- 字符串处理：
- 将数字以字符串形式读入，字符串的最后一个字符对应个位。
- 从字符串末尾向前遍历，按照当前位置与末尾的距离（即从右往左的第 $0, 1, 2, \ldots$ 位）判断奇偶，将对应数字分别累加到 $s_1$ 或 $s_2$ 中。
- 字符转数字的方法：
s[i] - '0'。
- 最终判断：
- 计算 $s_1 \mod 11$ 和 $s_2 \mod 11$，相等则输出
Yes，否则输出No。 - 由于每位数字最大为 $9$，最多 $100$ 位，所以 $s_1$ 和 $s_2$ 最大不超过 $9 \times 50 = 450$，用
int即可安全存储。
- 计算 $s_1 \mod 11$ 和 $s_2 \mod 11$，相等则输出
复杂度分析：
- 时间复杂度：$O(n \times L)$，其中 $L$ 为数字的位数，最大为 $100$。
- 空间复杂度：$O(L)$，用于存储输入的字符串。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <string>
int main() {
int n;
std::cin >> n;
while (n--) {
std::string x;
std::cin >> x;
int s1 = 0, s2 = 0;
int len = x.length();
// 从末尾（个位）向前遍历每一位数字
for (int i = len - 1; i >= 0; i--) {
// 计算当前位从右往左数的位置编号（个位为第0位）
int pos = len - 1 - i;
// 将字符转换为对应的数字
int digit = x[i] - '0';
if (pos % 2 == 0) {
// 偶数位（个位、百位、万位……）累加到 s1
s1 += digit;
} else {
// 奇数位（十位、千位、十万位……）累加到 s2
s2 += digit;
}
}
// 判断 s1 和 s2 对 11 取模是否相等
if (s1 % 11 == s2 % 11) {
std::cout << "Yes" << std::endl;
} else {
std::cout << "No" << std::endl;
}
}
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
"luogu-"系列题目可在洛谷题库进行在线评测。
"bcqm-"系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
