笔记汇总

结论：

若一个数 $N = p_1^{c_1} * p_2^{c_2} * … * p_k^{c_k}$

则满足约数个数 $ans = (c_1 + 1)(c_2 + 1)…(c_k + 1)$

证明

如果一个数有 $k$ 种质因子，每种质因子都有 $c_1, c_2, …, c_k$ 个。

每种质因子都可以选择 $0-c_i$ 个进行组合，也就是 $0-c_i$ 条出边。

根据乘法原理可知 约数个数 $ans = (c_1 + 1)(c_2 + 1)…(c_k + 1)$

快速求约数

若 $b$ 是 $a$ 的约数，则 $a$ 是 $b$ 的倍数。

预处理复杂度为 $O(nlogn)$

求约数 (1 ~ n)

预处理复杂度为 $O(nlogn)$

for (int i = 1; i <= n; i ++ )
    for (int j = i; j <= n; j += i)
        p[j].push_back(i);

约数个数 (1 ~ n)

预处理复杂度为 $O(nlogn)$

for (int i = 1; i <= n; i ++ )
    for (int j = i; j <= n; j += i)
        s[j] += i;

快除法求约数(n)

时间复杂度为 $O(\sqrt{n}/log(n))$

首先预处理出 $n$ 的所有质因数及其次数，用深搜枚举出 $n$ 的所有约数。

其中枚举质因数一步，可以优化为先枚举出所有 $0 - \sqrt{n}$ 的所有质数，再计算指数。

最大公约数

辗转相除法

此算法的关键在于证明:

$gcd(a, b) = gcd(b, a \% b)$

设 $gcd(a, b) = d$，则 $d \perp a$ && $d \perp b$

又因为 $a = c * b + a \% b$，其中 $c = a / b$

由 $a \perp d$ 和 $(c * b) \perp d$ 可知，$a - (c * b) = a \% b$ 可以整除 $d$

证必。

时间复杂度为 $O(logn)$

int gcd(int a, int b)
{
    if (!b) return a;
    return (b, a % b);
}

若扩展为多个数，则时间复杂度为 $O(nlogn)$

最小公倍数

一、 最小公倍数 = 两数乘积 / 最大公约数

二、分解质因数法：先列出相关数的质因数，最小公倍数等于所有的质因数的乘积。