算法基础课 第四讲 数学知识——约数

（比较简单，直接上代码，请谅解）

简介

约数，又称因数。整数$a$除以整数$b(b≠0)$除得的商正好是整数而没有余数，我们就说$a$能被$b$整除，或$b$能整除$a$。$a$称为$b$的倍数，$b$称为$a$的约数。在大学之前，”约数”一词所指的一般只限于正约数。约数和倍数都是二元关系的概念，不能孤立地说某个整数是约数或倍数。一个整数的约数是有限的。同时，它可以在特定情况下成为公约数。

试除法求所有约数

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

求约数个数

其中$a_1、a_2、a_3…a_k$是$p_1、p_2、p_3，…p_k$的指数。
对于一个大于$1$正整数$n$可以分解质因数：
$$n = \prod_{i=1}^{k}p_i^{a_i} = p_1^{a_1} · p_2^{a_2}......p_k^{a_k}$$
则n的正约数的个数就是:
$$f(n) = \prod_{i=1}^{k}(a_i+1) = (a_1+1)·(a_2+1)......(a_k+1)$$

具体实现

#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int N = 110, mod = 1e9 + 7;
int main()
{
    int n;
    cin >> n;
    unordered_map<int, int> primes;
    while (n -- )
    {
        int x;
        cin >> x;
        for (int i = 2; i <= x / i; i ++ )
            while (x % i == 0)
            {
                x /= i;
                primes[i] ++ ;
            }
        if (x > 1) primes[x] ++ ;
    }
    LL res = 1;
    for (auto p : primes) res = res * (p.second + 1) % mod;
    cout << res << endl;
    return 0;
}

求约数之和

$$n = \prod_{i=1}^{k}p_i^{a_i} = p_1^{a_1} · p_2^{a_2}......p_k^{a_k}$$

求最大公约数(欧几里得算法)

定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。

计算公式(核心)

$$gcd(a,b) = gcd(b,a mod b)$$

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