CSP-X 2018真题 | 11的倍数 luogu-B4075

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

3 
2035 
62202 
335 

输出 #1

Yes
No
No

说明/提示

对于 $30\%$ 的数据，$x_i$ 的位数不超过 $9$ 位；

对于 $50\%$ 的数据，$x_i$ 的位数不超过 $17$ 位；

对于 $100\%$ 的数据，$x_i$ 的位数不超过 $100$ 位，$n$ 不超过 $10$。

题目分析

本题考察的核心是11 的整除性判定法则以及大整数的字符串处理。由于输入数字最多可达 100 位，远超 long long 的表示范围（约 18 位），因此必须以字符串形式读入并逐字符处理。

解题思路分析：

1. 理解判定规则：

   • 从个位（最右边）开始，按位置的奇偶性将数字分为两组：个位、百位、万位……求和得 $s_1$；十位、千位、十万位……求和得 $s_2$。
   • 若 $s_1 \mod 11 = s_2 \mod 11$，则 $x$ 是 $11$ 的倍数。
   • 这本质上等价于判断 $s_1 - s_2$ 是否为 $11$ 的倍数（即奇偶位数字交替和能被 $11$ 整除）。

2. 字符串处理：

   • 将数字以字符串形式读入，字符串的最后一个字符对应个位。
   • 从字符串末尾向前遍历，按照当前位置与末尾的距离（即从右往左的第 $0, 1, 2, \ldots$ 位）判断奇偶，将对应数字分别累加到 $s_1$ 或 $s_2$ 中。
   • 字符转数字的方法：s[i] - '0'。

3. 最终判断：

   • 计算 $s_1 \mod 11$ 和 $s_2 \mod 11$，相等则输出 Yes，否则输出 No。
   • 由于每位数字最大为 $9$，最多 $100$ 位，所以 $s_1$ 和 $s_2$ 最大不超过 $9 \times 50 = 450$，用 int 即可安全存储。

复杂度分析：

• 时间复杂度：$O(n \times L)$，其中 $L$ 为数字的位数，最大为 $100$。
• 空间复杂度：$O(L)$，用于存储输入的字符串。

示例代码

#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;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号