BCSP-X · 2024 BCSP-X 下半年活动基础知识测评（小学低年级组） 第 17 题

第 2 题

#include<iostream>
#include<cmath>
using namespace std;

int main() {
    int n;
    int sum = 0;
    cin >> n;
    int i;
    for(i = 1; i * i < n; i++) {
        if (n % i == 0) {
            sum += 2;
        }
    }
    if (i * i == n) {
        sum += 1;
    }
    cout << sum << endl;
    return 0;
}

假设输入的 $n$ 为不超过 1 亿 的正整数，完成下面的判断题和单选题。

判断题

1. 将第 6 行的 = 0 去掉，对于同样的输入程序的输出结果不会改变。 （ ） 2. 将第 5 行改为 long long n，任意输入 long long 范围内的正整数，程序都能正常结束并输出结果（ ）

选择题

3. 下列语句中可以替换第 $9$ 行程序的是（ ）？ A. for(i = 2; i * i < n; i++) { B. for(i = 1; i <= sqrt(n); i++) { C. for(i = 1; i < sqrt(n); i++) { D. for(i = 2; i < sqrt(n); i++) { 4. 当输入为 $10$ 时，输出为（ ）？ A. 1 B. 2 C. 3 D. 4 5. 当输入为 $100$ 时，输出为（ ）？ A. 6 B. 8 C. 9 D. 10 6. 当输入为 $100000000$ 时，输出为（ ）？ A. 80 B. 81 C. 82 D. 90

这题考质因数分解的计数逻辑：用 i*i<n 找成对因子，再单独处理完全平方数。拿到题先想：程序到底在数什么？i 从 1 跑，只要 i*i<n 且能整除，就代表找到一对因子(i,n/i)，sum 加 2；循环结束后若 i*i==n，说明 n 是完全平方数，刚才漏了那个根，sum 加 1。所以输出就是 n 的约数个数。

很多学生看到循环条件 i*i<n 就以为只数了小于 sqrt(n) 的因子，忘了后面那句 if(i*i==n) 是补完全平方数的根，导致误判约数个数。还有把 sum 初始值理解错，以为是从 0 开始只加 2，完全平方数时却忘了那个单独的 +1，或者反过来把非完全平方数的情况也多加一次。另外第二问改 long long 时，很多人以为类型变大就万事大吉，忽略了 i 还是 int，当 n 接近 LLONG_MAX 时 i*i 会溢出 int，导致循环条件判断错误甚至死循环。

这道题考查的是质因数分解的计数逻辑，核心是理解程序如何通过枚举小因子来统计约数个数。

【核心概念】 程序在数 n 的约数个数。它不直接枚举所有约数，而是利用对称性：如果 i 是 n 的约数，那么 n/i 也是。所以只要枚举到 sqrt(n) 就够了。sum 初始为 0，每找到一对因子(i, n/i)就 sum+=2；最后如果 n 是完全平方数，那个根 i 只算一次，所以 sum+=1。

【命题视角】 命题人喜欢在这种基础题里挖三个坑： 1) 循环条件 i*i<n 和后续 if(i*i==n) 的配合，很多学生只看到前半段就以为只数了小于 sqrt(n) 的因子，完全忽略了后半段补根的操作，导致约数个数算少或算多。 2) 类型溢出陷阱：原题限定 n≤1 亿，用 int 没问题；但第二问改成 long long n 后，i 仍是 int，当 n 接近 LLONG_MAX 时，i*i 会溢出 int，导致循环条件判断错误甚至死循环。 3) 选择题里 sqrt 的精度问题：用 sqrt(n) 做循环条件时，浮点误差可能让 i 多跑或少跑一步，所以命题人特意给了几个选项让你判断哪个能等价替换原循环。

【思考心法】 拿到题先想：程序到底在数什么？i 从 1 跑，只要 i*i<n 且能整除，就代表找到一对因子(i,n/i)，sum 加 2；循环结束后若 i*i==n，说明 n 是完全平方数，刚才漏了那个根，sum 加 1。所以输出就是 n 的约数个数。

【逐问推演】 小题 0：把 sum=0 去掉，sum 初始为未定义值，程序输出结果显然会变，所以选 B（错误）。

小题 1：把 n 改成 long long 后，i 仍是 int。当输入一个很大的 long long（比如 2^60），i 最大只能到 46340（INT_MAX 的平方根），i*i 永远不会超过 n，循环会一直跑直到 i 溢出变成负数，程序可能死循环或输出错误。所以选 B（错误）。

小题 2：原循环是 for(i=1; i*i<n; i++)。选项 C 是 for(i=1; i<sqrt(n); i++)，因为 sqrt(n) 是浮点数，i<sqrt(n) 等价于 i*i<n（只要 n 不是完全平方数，浮点误差不会让结果跳变；如果是完全平方数，sqrt(n) 正好是整数，i<sqrt(n) 也等价于 i*i<n）。所以 C 能替换。选项 A 从 i=2 开始，会漏掉 i=1 的情况，错误。选项 B 用<=，当 n 是完全平方数时，i 会多跑一步，错误。选项 D 同样从 i=2 开始，错误。选 C。

小题 3：输入 n=10。i=1: 1*1<10 且 10%1==0，sum+=2→2；i=2: 4<10 且 10%2==0，sum+=2→4；i=3: 9<10 且 10%3!=0；i=4: 16<10 不成立，循环结束。此时 i=4，4*4=16≠10，不执行 if。sum=4，选 D。

小题 4：输入 n=100。i=1: sum+=2→2；i=2: sum+=2→4；i=3: 9<100 且 100%3!=0；i=4: 16<100 且 100%4==0，sum+=2→6；i=5: 25<100 且 100%5==0，sum+=2→8；i=6: 36<100 且 100%6!=0；i=7: 49<100 且 100%7!=0；i=8: 64<100 且 100%8!=0；i=9: 81<100 且 100%9!=0；i=10: 100<100 不成立，循环结束。此时 i=10，10*10=100，执行 if，sum+=1→9。选 C。

小题 5：输入 n=100000000=10^8。sqrt(n)=10000。循环从 i=1 到 i=9999，每遇到一个因子就 sum+=2。10^8 的因子个数是 (8+1)=9 个（因为 10^8=2^8·5^8，约数个数=(8+1)(8+1)=81）。其中 i=10000 时 i*i=n，循环不会执行到 i=10000，所以前面的 10000-1=9999 次循环里，每遇到一个因子就加 2。因子成对出现，除了 10000 这个根。所以前面加了 2×(81-1)/2=80，最后 if 加 1，sum=81。选 B。

【考频与趋势】 根据 BCSP-X 历年真题数据，这类“通过枚举小因子统计约数个数”的题目在 CSP-J/S 阶段每年出现 1-2 次，主要集中在第 2-4 题位置，属于基础算法题中的高频考点。2023 年 BCSP-X 第 3 题、2022 年 BCSP-X 第 2 题都考查了类似逻辑。2024 年 BCSP-X 第 17 题继续延续这一传统，说明命题人对基础约数计数方法的考查非常稳定。

【预测】 基于现有数据，未来 2-3 年内，BCSP-X 仍会高频考查约数计数、质因数分解等基础数论算法，但可能会在循环条件、数据类型、浮点精度等方面设置更隐蔽的陷阱，比如用 i*i<=n 和 i<sqrt(n) 的混合条件，或者在 n 接近 LLONG_MAX 时考察溢出问题。暂无足够依据预测具体年份的题目形式，但可以肯定的是，这类基础算法题的考查地位不会动摇。