INFO

若无特殊说明，本章涉及的变量皆为正整数。

定义

若 $n÷d$ 为整数，则 $d$ 是 $n$ 的因数，记作 $d\mid n$。

算数基本定理

任意正整数 $n$ 都能唯一地分解为有限个质数的乘积。

$$n=p_1^{c_1}\cdot p_2^{c_2}\cdots p_m^{c_m}$$

分解质因数

试除法

将 $n$ 分解成 算数基本定理 的形式，如

$$360=2^3\times 3^2\times 5$$

枚举 $i=2,3,\cdots ,\sqrt{n}$，除尽 $n$ 中的 $i$，并记录除的次数。

const int N = 1e6;
vector<int> P, C;

void factor(int n) {
    for (int i = 2; i <= sqrt(n); i ++) {
        if (n % i == 0) {
            P.push_back(i), C.push_back(1);
            while (n % i == 0)
                n /= i, C.back() ++;
        }
    }
    if (n != 1) {
        P.push_back(n);
        C.push_back(1);
    }
}

倍数法

求 $[1,n]$ 中各整数的因数集 $fact$，如

$$fact[12]=\{1,2,3,4,6,12\}$$

对各整数依次进行 试除法 效率差，此时考虑枚举每个数 $i$ 的倍数：

$i$ 的倍数必有因数 $i$。

枚举 $i=1,2,\cdots ,n$，并在 $i$ 的倍数的因数集中加入 $i$。

时间复杂度为 $O(n\log n)$。

const int N = 1e6;

vector<int> fact[N];

void factor(int n) {
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; i * j <= n; j ++) {
            fact[i * j].push_back(i);
        }
    }
}