跳到主要内容

AcWing 869. 试除法求约数

本节目标

用约数成对关系枚举并排序输出全部正约数。

本题利用质因数、约数与最大公约数中的因子对关系：找到一个小约数，就同时得到了对应的大约数。

查看 AcWing 原题

题意与约束​

对每个正整数输出全部正约数，结果必须递增。1 的约数表只有 [1]；平方数的平方根只能出现一次。

第一反应与瓶颈​

枚举 1..n 并检查整除会得到正确答案，但大约数与小约数成对，后半段搜索与前半段重复。我们只需遍历到平方根一侧。

数学关系与算法推导​

当 divisor 整除 n 时，n / divisor 也是约数。枚举所有满足 divisor <= n / divisor 的 divisor，同时收集两端；若两者相等，说明 n 是完全平方数，只加入一次。

这里以 divisor <= n / divisor 判断而不是直接比较 sqrt(n)。两种数学含义相同，但除法比较不会被浮点开方的舍入边界影响，也不会计算可能溢出的 divisor²。收集顺序交错，最后排序恢复递增输出。

正确性依据​

任一正约数 d 与 n / d 构成因子对，其中至少一个不大于 √n，因此枚举会遇到该对的较小者并加入两端。算法只在 d == n / d 时去重，恰好对应平方根这一对重合；所以不会遗漏也不会重复任何约数。排序仅改变输出顺序，不改变集合。

样例执行过程​

n = 36 时依次遇到 1、2、3、4、6，对应加入 36、18、12、9、6。6 是平方根只加入一次；排序后得到 1 2 3 4 6 9 12 18 36。

代码实现​

C++17
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

vector<int> enumerateDivisors(int n) {
    vector<int> divisors;

    for (int divisor = 1; divisor <= n / divisor; divisor++) {
        if (n % divisor != 0) {
            continue;
        }

        divisors.push_back(divisor);
        if (divisor != n / divisor) {
            divisors.push_back(n / divisor);
        }
    }
    sort(divisors.begin(), divisors.end());
    return divisors;
}

#ifndef ALGORITHM_TUTORIAL_TEST
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int count;
    cin >> count;
    while (count--) {
        int n;
        cin >> n;
        const vector<int> divisors = enumerateDivisors(n);
        for (int index = 0; index < static_cast<int>(divisors.size()); index++) {
            if (index > 0) {
                cout << ' ';
            }
            cout << divisors[index];
        }
        cout << '\n';
    }
}
#endif

enumerateDivisors／enumerate_divisors 返回有序约数表，入口只负责逐组输出空格分隔的结果。

复杂度分析​

枚举到平方根，时间复杂度为 O(√n)；保存答案占 O(τ(n)) 空间，其中 τ(n) 为约数个数。

边界与易错点​

  • 完全平方数不能把平方根加入两遍。
  • 不要假设收集过程天然递增，必须排序。
  • n = 1 会在第一轮加入自身，结果应为单元素表。
  • 避免使用 sqrt 浮点边界，使用整除关系控制循环更稳定。

模式迁移​

约数成对关系也可用于因子和、矩形尺寸枚举和整除 DP。若只需约数个数，可从质因数指数的乘积公式直接计算，而无需列出全部约数。