若整数 $n$ 除以整数 $d$ 余数为 $0$，即 $d$ 能整除 $n$，则称整数 $d$ 是整数 $n$ 的约数，$n$ 是约数 $d$ 的倍数。记为 $d\mid n$。

算术基本定理的推论

在算术基本定理中，若正整数 $n$ 能被唯一分解为 $p_1^{a_1}{p}_2^{a_2}\cdots p_k^{a_k}$，其中 $a_i$ 都是正整数，$p_i$ 是质数，且满足 $p_1<p_2<\cdots <p_k$，则 $n$ 的正约数集合可以写作：

$$\begin{gathered} p_1^{b_1}{p}_2^{b_2}\cdots p_k^{b_k} \\ \text{其中 }0\le b_i\le a_i \end{gathered}$$

$n$ 的正约数的个数为：

$$(a_1+1)\ast (a_2+1)\ast \cdots \ast (a_k+1)=\prod _{i=1}^k(a_i+1)$$

$n$ 的正约数的和为：

$$(1+p_1+p_1^2+\cdots +p_1^{a_1})\ast (1+p_2+p_2^2+\cdots +p_2^{a_2})\ast \cdots \ast (1+p_k+p_k^2+\cdots +p_k^{a_k})=\prod _{i=1}^k(1+p_i+p_i^2+\cdots +p_i^{a_i})=\prod _{i=1}^k(\sum _{j=0}^{a_i}{p}_i^j)$$

试除法求 $n$ 的约数集合

vector<int> factorize(int n) {
    vector<int> factor;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            factor.push_back(i);
            if (i != n / i) factor.push_back(n / i);
        }
    }

    return factor;
}

由试除法可知一个整数 $n$ 的约数个数上界为 $\sqrt{n}$，因此试除法的时间复杂度为 $O(\sqrt{n})$。

倍数法求 $1\sim n$ 每个数的约数集合

void factorize(int n) {
    vector<int> factor[500010];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n / i; j++) {
            factor[i * j].push_back(i);
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < factor[i].size(); j++) {
            cout << factor[i][j] << " ";
        }
        cout << endl;
    }
    return;
}

最大公约数和最小公倍数

若自然数 $d$ 同时是自然数 $a$ 和 $b$ 的约数，则称 $d$ 是 $a$ 和 $b$ 的公约数。在所有 $a$ 和 $b$ 的公约数中最大的一个，称为 $a$ 和 $b$ 的最大公约数，记作 $gcd(a,b)$。

若自然数 $d$ 同时是自然数 $a$ 和 $b$ 的公倍数，则称 $d$ 是 $a$ 和 $b$ 的公倍数。在所有 $a$ 和 $b$ 的公倍数中最小的一个，称为 $a$ 和 $b$ 的最小公倍数，记作 $\mathrm{lcm}(a,b)$。

最大公约数和最小公倍数的关系：

$$gcd(a,b)\ast \mathrm{lcm}(a,b)=a\ast b$$

更相减损术

$$\mathrm{\forall }a,b\in \mathbb{Z},a\ge bgcd(a,b)=gcd(a,a-b)=gcd(b,a-b)$$

欧几里得算法

$$\mathrm{\forall }a,b\in \mathbb{Z},gcd(a,b)=\{\begin{array}{ll}gcd(b,a\mathrm{mod}b)& \text{if }a\ge b\\ a& \text{if }b=0\end{array}$$

互质与欧拉函数

参见下节