CSP-J 2019 第一轮 第 21 题：程序（一）：多少长度时恰好最多36个字符不同

题目

#include <cstdio>
#include <cstring>
using namespace std;
char st[100];
int main() {
    scanf("%s", st);
    int n = strlen(st);
    for (int i = 1; i <= n; ++i) {
        if (n % i == 0) {
            char c = st[i - 1];
            if (c >= 'a')
                st[i - 1] = c - 'a' + 'A';
        }
    }
    printf("%s", st);
    return 0;
}

若输入的字符串长度为（），那么输入的字符串跟输出的字符串相比，至多有 $36$ 个字符不同。

选项

• A. 36
• B. 100000
• C. 1
• D. 128

答案

B

题解

按题目的考查意图，选 B．100000。

这段程序只会修改满足 n % i == 0 的位置，也就是 编号为字符串长度 \(n\) 的正因数的位置。

如果输入全是小写字母，这些位置都会变成大写字母。因此：

> 最多不同的字符数 = \(n\) 的正因数个数。

怎样计算正因数个数？若 \[ n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}, \] 则正因数个数为 \[ (a_1+1)(a_2+1)\cdots(a_k+1). \] 因为每个质因子的指数都可以从 \(0\) 选到 \(a_i\)，共有 \(a_i+1\) 种选择。

对比四个选项：

所以，最大值恰好是 \(36\) 时，选 B。

不过题面有两处不严谨：如果“至多36个”仅表示“不超过36个”，四个选项都满足；另外，st[100] 最多安全存放99个输入字符，长度100000会导致数组越界。这里应按“数组足够大，且最大不同字符数恰好为36”理解。