NOIP 提高组初赛 · NOIP 2012 提高组初赛试题 第 24 题

#include <iostream>
using namespace std;
int n, i, ans;
int gcd(int a, int b)
{
    if (a % b == 0) return b;
    else
        return gcd(b, a%b);
}
int main()
{
    cin>>n;
    ans = 0;
    for (i = 1; i <= n; i++)
        if (gcd(n,i) == i)
            ans++;
    cout<<ans<<endl;
}

输入：120 输出：________

别被代码绕晕，这题考的是数论里的正约数个数。看到 gcd(n,i)=i 直接反应出 i 是 n 的约数，这就把程序问题转化成了求 120 有多少个约数，用质因数分解公式秒杀。

学生最容易死磕代码里的递归 gcd 函数，甚至去模拟每一步取模运算，把简单问题复杂化。或者误以为 gcd(n,i)=i 只包含 1 和 n 自身，漏掉中间的约数。还有人会算错质因数分解，比如把 120 记成 2^2×3×5×5 或者指数搞错，导致因子个数公式里的 (指数+1) 乘起来出错。

程序阅读——正因子计数

程序功能：输入 n，统计满足 gcd(n,i)=i 的 i 的个数。 即：i 是 n 的正因子（i|n）的个数。

---

1. 考点与概念：什么是正因子

题目里的核心条件是 gcd(n, i) == i。在数论里，两个数的最大公约数等于其中较小的那个数，意味着较大的数一定能被较小的数整除。

换句话说，gcd(n, i) == i 等价于 i 能整除 n，也就是 i 是 n 的一个正因子。

所以这道题表面上是在跑一个求最大公约数的递归程序，实际上是在考：给定一个数 n，求它的正因子总共有多少个。

---

2. 命题视角：为什么考这个？

命题人很爱在初赛里用简单的程序结构（比如循环 + 条件判断）来包装一个纯粹的数论问题。这样做有两个目的：

• 考察信息素养：学生能不能快速透过代码看本质，不被递归函数吓住。
• 考察数论基础：正因子个数是数论里的基础公式，也是后续学习同余、欧拉函数、积性函数等更高级内容的基石。

这类题通常不会让你写代码，而是直接给一段伪代码或 C++ 代码，让你填空或输出结果。命题人喜欢挖坑的地方往往在：学生没反应过来条件等价于整除，或者质因数分解算错，又或者忘记因子个数公式是 (指数+1) 的乘积而不是指数的乘积。

---

3. 思考心法：拿到题先想什么？

拿到这道题，正确的思考路径应该是这样的：

1. 扫一眼代码逻辑： - 主函数读入 n，初始化 ans=0。 - 循环 i 从 1 到 n。 - 每次判断 gcd(n, i) == i，如果成立就 ans++。 - 最后输出 ans。

2. 翻译条件： - gcd(n, i) == i 意味着 i 整除 n。 - 所以程序在统计 n 的所有正因子个数。

3. 转化问题： - 题目变成：求 120 的正因子个数。

4. 调用工具： - 用质因数分解 + 因子个数公式秒杀。

---

4. 具体计算：120 的因子个数

第一步：质因数分解

120 可以分解为：

120 = 2 × 2 × 2 × 3 × 5 = 2³ × 3¹ × 5¹

第二步：应用因子个数公式

如果一个数 n 的质因数分解是 n = p₁^a₁ × p₂^a₂ × … × pₖ^aₖ，那么 n 的正因子个数 d(n) 等于：

d(n) = (a₁ + 1) × (a₂ + 1) × … × (aₖ + 1)

这是因为每个质因数 p_i 在组成因子时，可以取 0 到 a_i 次方，共 a_i + 1 种选择，而不同质因数的选择是独立的，所以用乘法原理。

代入 120 的分解结果：

• 2 的指数是 3 → (3 + 1) = 4
• 3 的指数是 1 → (1 + 1) = 2
• 5 的指数是 1 → (1 + 1) = 2

d(120) = 4 × 2 × 2 = 16

---

5. 避坑指南：学生最容易错在哪？

坑 1：死磕 gcd 函数

很多学生看到 gcd(n, i) == i 就一头扎进递归函数里，试图手动模拟每一步：gcd(120, 1) → gcd(1, 0) → 返回 1；gcd(120, 2) → gcd(2, 0) → 返回 2……

这是完全没必要且极其低效的。命题人给这段代码就是为了测试你是否能抽象出数学含义，而不是考你递归实现的细节。

坑 2：误以为只有 1 和 n

有些同学刚接触约数概念，容易把“约数”和“最大公约数”混淆，或者只记得 1 和自身是约数。他们可能会填 2，或者只算出 1 和 120 两个，漏掉中间的 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60。

坑 3：质因数分解错误

120 的分解是经典陷阱。有人会写成 2² × 3 × 5 × 5（把 2 的指数搞错成 2，把 5 的指数搞错成 2），或者忘记 5 是质数。分解错了，后面公式里的指数就全错。

坑 4：公式记错

最容易犯的错误是：把因子个数公式记成指数的乘积，即 3 × 1 × 1 = 3，或者 (3+1) × (1+1) × (1+1) 算成 4 × 2 × 2 = 16 时，中间某一步乘法出错。一定要记住：是 (指数+1) 的乘积，不是指数的乘积。

---

6. 考频与趋势

根据题库数据，整数与整除这一知识点共考过 9 题，覆盖 4 个考试级别（2009-2025）。

逐年分布：

• 2009 年：1 题
• 2010 年：1 题
• 2012 年：1 题
• 2021 年：2 题
• 2022 年：1 题
• 2023 年：2 题
• 2025 年：1 题

分赛事分布：

• CSP 入门级：3 题
• CSP 提高级：3 题
• NOIP 普及组 初赛：2 题
• NOIP 提高组 初赛：1 题

从数据看，这个知识点在 CSP 入门和提高级中占据重要位置，每年都有稳定出现，说明它属于基础中的基础，是每年必考或高频考点。

---

7. 预测

基于上述考频数据和历年趋势，可以合理预测：

• NOIP 提高组初赛中，这类“程序 + 数论”的题目（如本题）在未来几年仍会保持每年 1 题的频次，作为对基础数学和代码阅读能力的综合考察。
• CSP 提高级可能会继续增加此类题目的难度，比如给出更复杂的循环嵌套或更大的 n，要求考生快速写出约数个数公式或优化算法。
• CSP 入门级可能会延续目前的分布，每年 1-2 题，侧重考察基本的整除判断和简单的约数计算。

暂无足够依据预测该知识点会突然消失或大幅减少，因为它是数论的核心，也是信息学竞赛的基石之一。

---

答案：16

（程序统计的是 120 的正因子个数，120 = 2³ × 3 × 5，因子个数 = (3+1)(1+1)(1+1) = 16）