数学知识之约数

约数，又称因数，如果一个数 x 能被 k 整除（ x 是 k 的整数倍），那么 k 就是 x 的一个约数。

试除法求约数：

如果一个数有约数，那么约数一定是成对出现的，一个大于等于sqrt(x)，一个小于等于sqrt(x)；

若找到小于等于sqr(x)的约数，那么大于等于sqrt(x)的约数也被找到；

只需枚举1~sqrt(x)内的所有数，就可以求出x的所有约数；

时间复杂度为O(sqrt(n))。

1.代码模板如下：

void get_divisors(int x) {
    for (int i = 1; i <= x / i; i++) {
        if (x % i == 0) {//发现约数
            res[cnt++] = i;//i为约数
            if (x / i != i)res[j++] = x / i;//x/i也为约数
            //注意如果等于sqrt(x)的话就只有一个约数
        }
    }
}

求约数个数：

求一个数有多少个个约数，先将该数进行质因数分解：

数学知识之质数_如何何何的博客-CSDN博客

a = p1^α1 * p2^α2 * …… * pn^αn

约数个数就等于：

cnt = (α1+1) * (α2+1*) * …… * (αn+1)

注意：1需要特判，1不能被分解为质数，但约数个数为一。

1.代码模板如下：

void cnt_divisors(int x) {
    unordered_map<int, int>primes;//存储质因数分解的结果
 
    //分解质因数
    for (int i = 2; i <= x / i; i++) {
        if (x % i == 0) {
            while (x % i == 0) { primes[i]++; x /= i; }
        }
    }
    if (x > 1)primes[x]++;
 
    int res = 1;
    for (auto i = primes.begin(); i != primes.end(); i++)//遍历unordered_map
        res = (res * (i->second + 1)) % mod;//结果余上mod
 
    return;
}

2.拓展，一个数的约数个数为3说明：

该数的约数为1，sqrt(x)，x，且sqrt(x)为质数。

求约数之和：

求一个数的所有约数的和，同样先将该数进行分解质因数操作：

a = p1^α1 * p2^α2 * …… * pn^αn

约数之和就等于：

cnt = (p1^0 + p1^1 + …… + p1^α1) * (p2^0 + p2^1 + …… + p2^α2) *……* (pn^0 + pn^1 + …… + pn^αn)

1.代码模板如下：

void add_divisors(int x) {
    unordered_map<int, int>primes;//存储质因数分解的结果
 
    //分解质因数
    for (int i = 2; i <= x / i; i++) {
        if (x % i == 0) {
            while (x % i == 0) { primes[i]++; x /= i; }
        }
        if (x > 1)primes[x]++;
    }
 
    long long res = 1, tmp, cur;
    for (auto i = primes.begin(); i != primes.end(); i++) {//遍历所有质因数
        int a = i->first, p = i->second;//a^p
        cur = 1, tmp = a;
 
        while (p--) {
            cur = (cur + a) % mod;
            a = a * tmp % mod;
        }
 
        res = res * cur % mod;
    }
 
    return ;
}
 

求最大公约数：

使用欧几里得算法求最大公约数，也叫做辗转相除法。

a,b 的最大公约数等价于 b,a%b 的最大公约数。当 b(a%b) 等于 0 时，a 就是最大公约数。

 

1.代码模板如下：

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