约数（也叫因数）的定义大家肯定也都知道。

第一个知识点：求一个数的所有约数——试除法

跟分解质因数差不多，也都是枚举到 $\sqrt n$ 就行了，大于 $\sqrt n$ 的直接算就行了，反正约数都是成对成对地出现的。

vector< int > get_divisors(int n){
    vector< int > ans;
    for (int i = 1; i <= n / i; i++){
        if (n % i == 0){
            ans.push_back(i);
            if (i != n / i) ans.push_back(n / i);
        }
    }
    sort(ans.begin(), ans.end());
    return ans;
}

第二个知识点：约数个数和约数之和——公式

假如一个数 $n$ 分解质因数是这样的形式：
$$P_1^{\alpha_1} \cdot P_2^{\alpha_2} \cdots P_k^{\alpha_k}$$
那么对于 $n$ 的一个约数就应该是这种形式：
$$P_1^{\beta_1} \cdot P_2^{\beta_2} \cdots P_k^{\beta_k} (0 \leq \beta_i \leq \alpha_i)$$
然后就可以通过乘法原理来求出因数个数，每一个 $\beta_i$ 的个数都是 $\alpha_i+1$ 然后把所有的 $\alpha_i+1$ 乘起来，就是约数个数，公式是：
$$(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)$$
举个例子，$540 = 2^2 \times 3^3 \times 5^1$。
在这里：
$$\begin{aligned} (\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1) &= (2+1) \times (3+1) \times (1+1) \\ &= 3 \times 4 \times 2 \\ &= 24 \end{aligned}$$
就说明 $540$ 的因数个数是 $24$，我们枚举一下试试看：$1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 27, 30, 36, 45, 54, 60, 90, 108, 135, 180, 270, 540$
恰好 $24$ 个。

再看约数之和，首先，约数之和的求法是这样（假设分解质因数还是上面的形式）：
$$(P_1^0+P_1^1+\cdots+P_1^{\alpha_1})(P_2^0+P_2^1+\cdots+P_2^{\alpha_2})\cdots(P_k^0+P_k^1+\cdots+P_k^{\alpha_k})$$
那为什么是这样也很简单，直接用乘法分配律展开，然后就会得到一堆两个数的乘积加在一起，我们可以惊奇的发现，每一个乘积都是 $n$ 的其中一个约数，正好把它们加到了一块，这就是约数之和。

代码就不写了吧，这么简单。

第三个知识点：求最大公因数——欧几里得算法（辗转相除法）

首先我们要了解一些性质，如果 $d$ 能整除 $a$，$d$ 也能整除 $b$，那么 $d$ 就能整除 $ax + by（x, y 均为整数）$。
而且，$b$ 和 $a$ 的最大公因数，就等于 $a$ 和 $b \bmod a$ 的最大公因数，我们可以把 $b \bmod a$ 写成 $b - a \times \lfloor \frac{b}{a} \rfloor$ 的形式，假设我们把 $\lfloor \frac{b}{a} \rfloor$ 写成 $c$，那么 $b$ 和 $a$ 的最大公约数就要证明一下是不是跟 $a$ 和 $b - a \times c$ 的最大公约数是相等的。
假设 $d$ 是 $b$ 和 $a$ 的最大公约数，根据最上面的性质，$d$ 能整除 $b$，$d$ 能整除 $a$，那么 $d$ 就能整除 $b \times 1 + a \times (-c)（毕竟 c 还是一个整数）$，也就相当于 $d$ 能整除 $b - a \times c$，所以就证明完了。

int gcd(int a, int b){
    if (b == 0) return a; //  如果 b == 0，那么 a 和 0 的最大公约数肯定就是 a 因为 0 能整除任何数
    return gcd(b, a % b);
}

更简洁的就是这样：

int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}