约数

试除法求约数

一个数的约数是成对出现的，同时只有一个大于 $\sqrt{n}$ 的约数。

void get_divisors(int n) {
    vector<int> res;

    for (int i = 1; i <= n / i; i ++) {
        if (n % i == 0) {
            res.push_back(i);

            if (i != n / i) {
                res.push_back(n / i); // avoid i * i == n
            }
        }
    }

    sort(res.begin(), res.end());

    for (auto t : res) {
        cout << t << " ";
    }
    cout << endl;
}

AC869. 试除法求约数

如何计算时间复杂度？首先思考 $1\sim n$ 中每个数的约数个数：

• $1$ 是所有数的约数
• $2$ 是所有它的倍数的约数
• $k$ 是所有它的倍数的约数
• $1\sim n$ 中每个数的约数个数之和等价于每个数的倍数之和

也就是：

$$n+\frac{n}{2}+\frac{n}{3}+\cdots +\frac{n}{n}=n(1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n})\approx n\ln n$$

期望来看，每个数的约数个数就是 $\ln n$ 个。

总的时间复杂度为 $O(\sqrt{n})+O(n\log \ln n)$，舍去后面的，也就是 $O(\sqrt{n})$。

约数个数

对于某个自然数 $N$ 的质因数分解：

$$N=p_1^{{\alpha }_1}\times p_2^{{\alpha }_2}\times \cdots \times p_k^{{\alpha }_k}$$

它的所有约数个数为（简单的乘法原理）：

$$({\alpha }_1+1)({\alpha }_2+1)\cdots ({\alpha }_k+1)$$

AC870. 约数个数

约数之和

由于所有的约数为 $p_i^{{\beta }_i}$，因此所有约数之和为：

$$\prod _{i=1}^k\sum _{j=0}^{{\alpha }_i}{p}_i^j=(p_1^0+p_1^1+\cdots +p_1^{{\alpha }_1})\cdots (p_k^0+p_k^1+\cdots +p_k^{{\alpha }_k})$$

证明很显然，直接展开就可以，每一项都是约数。

核心代码：

// ...
    for (auto prime : primes) {
        int p = prime.first;
        int a = prime.second;

        long long t = 1;

        while (a --) {
            t = (t * p + 1) % mod;
        }

        res = res * t % mod;
    }

这里是对于：

$$p^0+p^1+p^2+p^3=1+(1+(1+p)p)p$$

的扩展。

TODO：这个算法还有 $\log a$ 的时间复杂度方法。

AC871. 约数之和

最大公约数

求最大公约数的算法就是 欧几里得算法/辗转相除法。

首先我们知道，如果 $d|a,d|b$，也就是说 $d$ 是 $a,b$ 的公约数，那么 $d|a+b,d|ax+by$。

我们常用 (a, b) 表示 a 和 b 的最大公约数 GCD。

辗转相除法的算法核心：(a, b) = (b, a mod b)，证明：

• a mod b 可以看作是 a 不断地减去 b，直到不能减为止，不妨记为 a - c * b
• 设 d 是 a, b 的任何一个公约数，那么 d | b, d | a - c * b，即它是右边的公约数
• 设 d 是 b, a mod b 的任何一个公约数，那么由于 a = (a - c * b) + c * b，因此 d | a，即它也是左边的公约数
• 因此左右两侧的所有公约数都相同，那么最大公约数自然也相同

核心代码：

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

有几个注意事项：

• 当 a < b 时，a mod b 得到的结果中 a - c * b 中的 c == 0，下一轮调换位置
• 当 a % b == 0 时，说明此时 b 就是二者的最大公约数，根据 (a, b) = (b, 0) 下一轮直接输出

AC872. 最大公约数