三十四、数学知识——约数（试除法 + 约数个数 + 约数之和 + 欧几里得算法）

一、基本思路

1、定义

• 约数：
• • 约数是指一个数（因数）能整除另一个数的正整数，也称为因数。
• 举例：
• • “||”表示整除，a||b,即为 a 整除 b ，则，b/a为一个整数。

2、试除法——求一个数的所有约数

• (d || n) ==> (n/d || n) ==> (d <= n/d) ==> (d <= sqrt(n))
• 其中 d 与 n/d 都是 n 的约数，并且成对出现，我们需要成对储存
• 但是需要特判一种情况—— i ?= n/i

3、约数个数

• 质因数（正整数）分解定理：
  
• 约数个数定理：
  
• 问题：是否可以用试除法求解约数个数？
• • 理论上暴力求解可以，但是稍微大一点的数就会极容易溢出。

4、约数之和

• 约数之和定理：
  
• 求解技巧：
  

5、欧几里得算法——辗转相除法（求解最大公约数）

• 基本性质：
• • (d||a ， d||b) ⇒ (d||ax+by);
• 核心原理：
• • (a, b)代表求解 a，b的最大公约数
• • (a, b) = (b , a mod b)
• 欧几里得算法原理证明：

二、Java、C语言模板实现

// java 模板
// 1、试错法求解约数
static void getDiv(int n){
  PriorityQueue<Integer> q = new PriorityQueue<Integer>();        
  // 优先队列，Integer已经实现了Comparable接口，可以实现自动排序
  int count = 0;
  for(int i = 1; i <= n/i; i++){         // i 与 n/i 成对存在，能成为n的约数，那么n/i也可以是
     if(n % i == 0){                     // 满足整除条件，则为约数
         q.add(i);
         count++;
         if(i != n/i){            // 如果满足条件，那么就是与之对应的另一对约数，不满足则重复了
               q.add(n/i);
               count++;
         }
     }
  }
        
 for(int i = 0; i < count; i++){
     System.out.print(q.poll() + " ");
  }   
}

// 2、约数个数求解
for(int ii = 0; ii < n; ii++){
   int x = Integer.parseInt(reader.readLine());
            
   // 此处使用的是分解质因数的模板，得到的每个数的质因数以及指数
   for(int i = 2; i <= x/i; i ++){
       while(x % i == 0){
            x /= i;
            map.put(i, map.getOrDefault(i, 0) + 1);
       }
   }
            
   if(x > 1){
      map.put(x, map.getOrDefault(x, 0) + 1);
   }
}
        
   long res = 1;
        
   for(int value : map.values()){
       res = res * (value + 1) % Mod;          
       / 此处一边相乘，一边mod，是因为一旦数字变大，就会导致溢出，影响最后的结果
   }

// 3、约数之和求解
for(int ii = 0; ii < n; ii++){
   int x = Integer.parseInt(reader.readLine());
            
   // 此处使用的是分解质因数的模板，得到的每个数的质因数以及指数
   for(int i = 2; i <= x/i; i ++){
      while(x % i == 0){
           x /= i;
           map.put(i, map.getOrDefault(i, 0) + 1);
      }
   }
            
   if(x > 1){
      map.put(x, map.getOrDefault(x, 0) + 1);
   }
        
   // map 中存储的是键值对————质因数pi与质数ai
        
   long res = 1;
        
   for(int key : map.keySet()){
      long t = 1;
      int value = map.get(key);
            
      while(value-- > 0){
          t = (t * key + 1) % Mod;        // 进行取模运算是为了防止溢出
      }
            
      // 此处模仿了 p^0 + p^1 +...+p^a
      // t = 1;
      // t = p + 1;
      // t = p^2 + p + 1;
      // t = p^3 + p^2 + p + 1;
            
     res = res*t % Mod;
  }

// 4、最大公约数————欧几里得算法
static int gcd(int a, int b){
    // 用到了递归思想 + 欧几里得算法公式
    return b != 0 ? gcd(b, a % b) : a;      // 应该是b不等0的时候呀，满足第一个表达式，等于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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

// C++ 模板，由yxc实现
// 1、试错法求解约数
试除法求所有约数 —— 模板题 AcWing 869. 试除法求约数
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;
}

// 2、约数个数求解  约数之和求解
约数个数和约数之和 —— 模板题 AcWing 870. 约数个数, AcWing 871. 约数之和
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

// 3、最大公约数————欧几里得算法
欧几里得算法 —— 模板题 AcWing 872. 最大公约数
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

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

三、例题题解

// java题解实现
import java.util.*;

public class Main{
    
    
    static void getDiv(int n){
        PriorityQueue<Integer> q = new PriorityQueue<Integer>();        
        // 优先队列，Integer已经实现了Comparable接口，可以实现自动排序
        int count = 0;
        for(int i = 1; i <= n/i; i++){          // i 与 n/i 成对存在，能成为n的约数，那么n/i也可以是
            if(n % i == 0){                     // 满足整除条件，则为约数
                q.add(i);
                count++;
                if(i != n/i){                   // 如果满足条件，那么就是与之对应的另一对约数，不满足则重复了
                    q.add(n/i);
                    count++;
                }
            }
        }
        
        for(int i = 0; i < count; i++){
            System.out.print(q.poll() + " ");
        }
        System.out.println();
        
    }
    
    
    public static void main(String[] args){
        Scanner in  = new Scanner(System.in);
        
        int n = in.nextInt();
        
        for(int i = 0; i < n; i++){
            int ai = in.nextInt();
            getDiv(ai);
        }
    }
}

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

import java.util.*;
import java.io.*;

public class Main{
    static long Mod = (long)1e9 + 7;
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        HashMap<Integer,Integer> map = new HashMap<>();     
        // 用HashMap是因为键值key是唯一的，也就意味着我们先将每个数分解成质因数和指数形式即可
        // 因为质因数分解和本题中的各个数之间关系都是相乘
        // 因此在相同key的对应的不同指数就含有了不同数相乘信息
        
        int n = Integer.parseInt(reader.readLine());
        
        for(int ii = 0; ii < n; ii++){
            int x = Integer.parseInt(reader.readLine());
            
            // 此处使用的是分解质因数的模板，得到的每个数的质因数以及指数
            for(int i = 2; i <= x/i; i ++){
                while(x % i == 0){
                    x /= i;
                    map.put(i, map.getOrDefault(i, 0) + 1);
                }
            }
            
            if(x > 1){
                map.put(x, map.getOrDefault(x, 0) + 1);
            }
        }
        
        long res = 1;
        
        for(int value : map.values()){
            res = res * (value + 1) % Mod;          
            // 此处一边相乘，一边mod，是因为一旦数字变大，就会导致溢出，影响最后的结果
        }
        
        
        System.out.println(res);
    }
    
}
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

import java.util.*;
import java.io.*;

public class Main{
    static long Mod = (long)1e9 + 7;
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        HashMap<Integer,Integer> map = new HashMap<>();     
        // 用HashMap是因为键值key是唯一的，也就意味着我们先将每个数分解成质因数和指数形式即可
        // 因为质因数分解和本题中的各个数之间关系都是相乘
        // 因此在相同key的对应的不同指数就含有了不同数相乘信息
        
        int n = Integer.parseInt(reader.readLine());
        
        for(int ii = 0; ii < n; ii++){
            int x = Integer.parseInt(reader.readLine());
            
            // 此处使用的是分解质因数的模板，得到的每个数的质因数以及指数
            for(int i = 2; i <= x/i; i ++){
                while(x % i == 0){
                    x /= i;
                    map.put(i, map.getOrDefault(i, 0) + 1);
                }
            }
            
            if(x > 1){
                map.put(x, map.getOrDefault(x, 0) + 1);
            }
        }
        
        // map 中存储的是键值对————质因数pi与质数ai
        
        long res = 1;
        
        for(int key : map.keySet()){
            long t = 1;
            int value = map.get(key);
            
            while(value-- > 0){
                t = (t * key + 1) % Mod;        // 进行取模运算是为了防止溢出
            }
            
            // 此处模仿了 p^0 + p^1 +...+p^a
            // t = 1;
            // t = p + 1;
            // t = p^2 + p + 1;
            // t = p^3 + p^2 + p + 1;
            
            res = res*t % Mod;
        }
        
        
        System.out.println(res);
    }
    
}
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
51
52
53
54
55
56
57

import java.util.*;
import java.io.*;

public class Main{
    
    static int gcd(int a, int b){
        // 用到了递归思想 + 欧几里得算法公式
        return b != 0 ? gcd(b, a % b) : a;      // 应该是b不等0的时候呀，满足第一个表达式，等于0满足第二个表达式
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(in.readLine());
        
        for(int i = 0; i < n; i++){
            String[] str = in.readLine().split(" ");
            int a = Integer.parseInt(str[0]);
            int b = Integer.parseInt(str[1]);

            System.out.println(gcd(a, b));
        }
        
    }
}
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