求约数

求一个数的所有约数枚举 $[1,\sqrt{n}]$ 的所有整数能整除 n 的就是约数另一半约数就是 n / i.

vector<int> 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);
        }
    }
    return res;
}

约数个数

求约数个数基于约数个数定理

对于一个大于 $1$ 的正整数 $n$ 可以分解质因数
$$n=\prod _{i=1}^k{p}_i^{a_i}=p_1^{a_1}\cdot p_2^{a_2}\cdot \cdots \cdot p_k^{a_k}$$
则 $n$ 的正约数的个数是
$$d(n)=\prod _{i=1}^k(a_i+1)=(a_1+1)(a_2+1)\cdots (a_k+1)$$
证明

$p_1^{a_1}$ 的约数有 $p_1^0,p_1^1,p_1^2,\cdots ,p_1^{a_1}$ 共 $a_1+1$ 个同理 $p_k^{a_k}$ 的约数有 $a_k+1$ 个。

由乘法原理$n$ 的约数个数就是 $(a_1+1)(a_2+1)\cdots (a_k+1)$

代码

其实和质因数分解很相似只要会质因数分解就会求因数个数

int num_divisors(int n) {
    int res = 1;
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            int s = 0;
            while (n % i == 0) {
                n /= i;
                ++s;
            }
            res *= s + 1;
        }
    }
    if (n > 1) res *= 2;
    return res;
}

约数之和

对于一个大于 $1$ 的正整数 $n$ 可以分解质因数
$$n=\prod _{i=1}^k{p}_i^{a_i}=p_1^{a_1}\cdot p_2^{a_2}\cdot \cdots \cdot p_k^{a_k}$$
n 的约数之和是
$$\sigma (n)=(p_1^0+p_1^1+p_1^2+\cdots +p_1^{a_1})(p_2^0+p_2^1+p_2^2+\cdots +p_2^{a_2})\cdots (p_k^0+p_k^1+p_k^2+\cdots +p_k^{a_k})$$
等比数列求和上式可以写成
$$\sigma (n)=\frac{p_1^{a_1+1}-1}{p_1-1}\times \frac{p_2^{a_2+1}-1}{p_2-1}\times \cdots \times \frac{p_k^{a_k+1}-1}{p_k-1}$$
代码

int sum_divisors(int n) {
    int res = 1;
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            int s = i;
            while (n % i == 0) {
                n /= i;
                s *= i;
            }
            res *= (s - 1) / (i - 1);
        }
    }
    if (n > 1) res *= (n * n - 1) / (n - 1);
    return res;
}

最大公约数

欧几里得算法

欧几里得算法又称辗转相除法计算公式为 $\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$

假如需要求 $1997$ 和 $615$ 两个正整数的最大公约数,用欧几里得算法是这样进行的

$1997÷615=3(余152)$

$615÷152=4(余7)$

$152÷7=21(余5)$

$7÷5=1(余2)$

$5÷2=2(余1)$

$2÷1=2(余0)$

至此最大公约数为 $1$

以除数和余数反复做除法运算当余数为 $0$ 时取当前算式除数为最大公约数所以就得出了 $1997$ 和 $615$ 的最大公约数 $1$。

代码

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