一篇文章搞懂约数——试除法求约数、约数个数、约数之和

试除法求约数

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

例题：

#include 
#include 
#include 

using namespace std;

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;
}

int main()
{
    int n;
    cin >> n;
    
    while(n--)
    {
        int x;
        cin >> x;
        
        auto res = get_divisors(x);
        
        for(auto x : res) cout << x << ' ';
        cout << endl;
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

约数个数

算数基本定理：N = p1^a1 * p2^a2 * … * pk^ak
那么约数的个数 ans = (a1 + 1)(a2 + 1)(a3 + 1)…(ak + 1)；0 <= Bi <= ai
因为任何一个约数d都可以表示d = p1^b1 * p2^b2 * … * pk^bk，如果每一项Bi都不同，那么约数d就不同
B1共有 0 ~ a1种选法
B2共有 0 ~ a2种选法
…

例题：

#include 
#include //底层哈希表
#include 
#include 

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)
            {
                primes[i]++;//i的质因数指数+1
                x /= i;
            }
        }
        if(x > 1) primes[x]++;//x的最大公约数大于 sqrt（x）
    }
    
    LL res = 1;
    for(auto p : primes) res = res * (p.second + 1) % mod;//公式
    
    cout << res << endl;
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

约数之和

算法基本定理：N = p1^a1 * p2^a2 * … * pk^ak
约数之和的公式：
ans = (p1^0 + p1^1 + … + p1^k) * … * (pk^0 + pk^1 + … + pk^k)

例题：

#include 
#include 
#include 
#include 

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]++;//指数+1
            }
        }
        
        if(x > 1) primes[x]++;
    }
    
    LL res = 1;
    for(auto p : primes)
    {
        LL a = p.first, b = p.second;
        LL t = 1;
        //1.t = p1^1 + p1^0
        //2.t = p1^2 + p1^1 + p1^0
        //......
        //+1就是代表了p1^0这一项p1果不会溢出
        res = res * t % mod;
    }
    
    cout << res << endl;
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

总结

• 算数基本定理：N = p1^a1 * p2^a2 * … * pk^ak
• 约数个数：ans = (a1 + 1)(a2 + 1)(a3 + 1)…(ak + 1)
• 约数之和：ans = (p1^0 + p1^1 + … + p1^k) * … * (pk^0 + pk^1 + … + pk^k)