NOIP 提高 2012 第一轮 第 24 题：欧几里得 gcd 统计约数个数

题目

```
#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  
输出：________

请写出程序的输出结果。

答案

16

题解

考点定位

本题考「gcd 递归与约数」,对应大纲 2.1.3 初等数论（难度【3】）。

解题过程

gcd(n,i)==i ⟺ i 整除 n 且 gcd 恰为 i——即 i 是 n 的约数。统计 120 的约数个数：

$$120=2^3\times3\times5\;\Rightarrow\;(3+1)(1+1)(1+1)=16$$

答案：16。

易错提醒

① gcd(120,i)=i ⟺ i|120（gcd 与较小数相等的条件）；② 约数个数公式 Π(指数+1)。