解题思路

如果一个整数 d 能整除 x（也就是 x % d == 0，余数为 0），那么 d 就是 x 的因数。题目要求用函数 func(x) 来求一个数 x 的因数个数。

求因数个数的方法很简单：从 1 到 x 一个一个试，只要能整除 x，个数就加 1。

例如 x = 3：1 能整除 3，2 不能，3 能整除，所以因数有 1、3，共 2 个。 例如 x = 6：1、2、3、6 都能整除 6，共 4 个。

题目要计算 4 个整数的因数个数之和，所以我们把 func(a) + func(b) + func(c) + func(d) 加起来就是答案。

验证一下样例 3 6 8 5：

• func(3) = 2（因数 1、3）
• func(6) = 4（因数 1、2、3、6）
• func(8) = 4（因数 1、2、4、8）
• func(5) = 2（因数 1、5）
• 总和 = 2 + 4 + 4 + 2 = 12，和样例输出一致。

题目要求“计算一个整数的因数个数用函数 func() 实现”，所以我们一定要把统计因数的代码写进函数里。

参考代码

// P4594 因数个数之和：用函数 func() 统计每个整数的因数个数并求和
#include <iostream>
using namespace std;

// 返回整数 x 的因数个数
int func(int x) {
    int cnt = 0;                      // cnt 记录因数个数
    for (int i = 1; i <= x; i++)      // 从 1 试到 x
        if (x % i == 0) cnt++;        // i 能整除 x，说明 i 是 x 的因数
    return cnt;
}

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;          // 输入 4 个整数
    // 四个数的因数个数相加
    cout << func(a) + func(b) + func(c) + func(d) << endl;
    return 0;
}

复杂度分析

数字最大不超过 10000。func(x) 要从 1 试到 x，时间是 O(x)。一共 4 个数，所以总时间大约是 O(4 × 10000)，对于电脑来说一下子就完成了。只用几个变量，空间是 O(1)。