约数

$1 \sim n$中的约数个数为存在倍数的个数
$n + \frac{n}{2} + \dots + \frac{n}{n} = n\lg n$
每个数的期望约数个数为$O(\lg n)$

求一个数的所有约数 - 试除法

试除$d$，使得$d | n$，则必然有$\frac{n}{d} | n$，所以约数在不等于$\sqrt n$的情况下，是成对出现的

因此只要枚举
$$ d \leq \frac{n}{d} \rightarrow d \leq \sqrt n $$

for (int i = 1; i <= n / i; i++) {
    if (n % i == 0) {
        list.add(i);
        if (i !=  n / i) list.add(n / i); // 防止同一个约数被加入两次
    }
}

约数个数

一个数可以分解质因数，因此可以表示为$N = p_1^{\alpha_1} p_2^{\alpha_2}\dots p_k^{\alpha_k}$
则约数个数为$$(\alpha_1+1)(\alpha_2+1)\dots(\alpha_k+1)$$

因为约数$d$也可以表示为$d = p_1^{\beta_1} p_2^{\beta_2}\dots p_k^{\beta_k}$且$0\leq\beta_i\leq\alpha_i$,因此所有约数的个数为$\beta_1\sim\beta_k$的所有可能选法

代码实现

int范围内约数最多约为1600个

约数之和

同样可以分解质因数

因此约数之和为
$$(p_1^0 + p_1^1 + \dots p_1^{\alpha_1})(p_2^0 + p_2^1 + \dots p_2^{\alpha_2}) \dots (p_k^0 + p_k^1 + \dots p_k^{\alpha_k})$$

将其展开可以得到累和的每一项为$p_1^{\beta_1}+p_2^{\beta_2}+\dots p_k^{\beta_k}, 0 \leq \beta_1 \leq \alpha_1, \dots 0 \leq \beta_k \leq \alpha_k$

且总共有$(\alpha_1+1)(\alpha_2+1)\dots(\alpha_k+1)$项，且每一项都为该数的约数，实际上等价于约数之和

代码实现

欧几里得算法(辗转相除法)

$$d | x, d | y \rightarrow d | ax + by$$

$(a, b)$代表$a$和$b$的最大公约数，则有
$$(a, b) = (b, a \bmod b)$$

证明：
$a \bmod b = a - \lfloor \frac{a}{b} \rfloor \cdot b = a - c \cdot b$因此表达式等价有$(b, a \bmod b) = (b, a - c \cdot b)$

若约数$d$有$d | a, d |b $也必有$d | b, d | a - c \cdot b$，相反也成立，因此左右的的公约数集合相等，所以左右两边的最大公约数相等

int gcd(int a, int b) {
    return b != 0 ? gcd(b, a % b) : a; // 当b = 0时，由于0能整除任何数，因此(a, 0) = a， 0 <= a % b <= a
}

$a, b$的所有公约数等价于$gcd(a, b)$的所有公约数
Acwing 4199

最小公倍数

$a$和$b$的最小公倍数为$\frac{a \times b}{(a, b)}$

int res = a * gcd(a, b) / b; // 调整顺序防止爆int

注意中间结果的数据范围，爆int需要使用long