CSP-J 2022 第一轮 第 39 题：枚举因数：⑤处应填

题目

（枚举因数）从小到大打印正整数 $n$ 的所有正因数。

试补全枚举程序。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;

    vector<int> fac;
    fac.reserve((int)ceil(sqrt(n)));

    int i;
    for (i = 1; i * i < n; ++i){
        if (①){
            fac.push_back(i);
        }
    }

    for (int k = 0; k < fac.size(); ++k){
        cout << ② << "";
    }
    if (③) {
        cout << ④ << "";
    }
    for (int k = fac.size() - 1; k >= 0; --k){
        cout << ⑤ << "";
    }
}

⑤处应填（ ）

选项

• A. n / fac[k]
• B. fac[k]
• C. fac[k]-1
• D. n / (fac[k]-1)

答案

A

题解

选 A：n / fac[k]。

因数总是成对出现：如果 d 是 n 的因数，那么 n / d 也是。

前面的循环把小于 $\sqrt n$ 的因数从小到大存进 fac。最后一个循环倒序遍历 fac，输出对应的 n / fac[k]，就能让大于 $\sqrt n$ 的因数也从小到大输出。

例如 n = 36：

• fac 中存的是 1, 2, 3, 4；
• 先输出这些小因数，再单独输出平方根 6；
• 倒序取 4, 3, 2, 1，输出 36 / 4, 36 / 3, 36 / 2, 36 / 1，即 9, 12, 18, 36。

因此⑤应填： ``cpp n / fac[k] ``