Acwing - 算法基础课 - 笔记（十）

悠悠 2023-01-23 14:48 9阅读 0赞

### 文章目录 ###

*   *  数学知识（一）
     *   *  质数
         *   *  质数的判定
             *  分解质因数
             *   *  朴素思路
                 *  优化
             *  筛选质数
             *   *  朴素筛法
                 *  埃氏筛法
                 *  线性筛法
                 *  小结
         *  约数
         *   *  求一个数的所有约数
             *  求约数个数
             *  求约数之和
             *  求最大公约数

数学知识章节，主要讲解了

*  数论
 *  组合计数
 *  高斯消元
 *  简单博弈论

## 数学知识（一） ##

这一小节主要讲解的是数论，主要包括了质数，约数，欧几里得算法。

### 质数 ###

对所有的大于1的自然数字，定义了【质数/合数】这一概念。对于所有小于等于1的自然数，没有这个概念，它们既不是质数也不是合数。

质数的定义：对于大于1的自然数，如果这个数的约数只包含1和它本身，则这个数被称为质数，或者素数

#### 质数的判定 ####

采用试除法。

对于一个数n，从2枚举到n-1，若有数能够整除n，则说明除了1和n本身，n还有其他约数，则n不是质数；否则，n是质数

优化：由于**一个数的约数都是成对出现的**。比如12的一组约数是3，4，另一组约数是2，6。则我们只需要枚举较小的那一个约数即可

我们用 d ∣ n d | n d∣n来表示d整除n，比如 3 ∣ 12 3|12 3∣12

只要满足 d ∣ n d|n d∣n，则一定有  n d ∣ n \\frac\{n\}\{d\} | n dn∣n，因为约数总是成对出现的

比如 3 ∣ 12 3|12 3∣12，就一定有 4 ∣ 12 4|12 4∣12

我们只枚举小的那一部分的数即可，令 d ≤ n d d \\le \\frac\{n\}\{d\} d≤dn，则  d ≤ n d \\le \\sqrt\{n\} d≤n

则对于数n，只需要枚举2到 n \\sqrt\{n\} n 即可

bool is_prime(int n) { 
        if(n < 2) return false;
        for(int i = 2; i <= n / i; i++) { 
            if(n % i == 0) return false;
        }
        return true;
    }

注意有一个细节，for循环的结束条件，推荐写成`i <= n / i`。

有的人可能会写成`i <= sqrt(n)`，这样每次循环都会执行一次`sqrt`函数，而这个函数是有一定时间复杂度的。而有的人可能会写成

`i * i < =n`，这样当`i`很大的时候（比如`i`比较接近`int`的最大值时），`i * i`可能会溢出，从而导致结果错误。

练习题：[acwing - 866: 试除法判定质数][acwing - 866_]

#include<iostream>
    using namespace std;
    
    bool is_prime(int n) { 
    	if(n < 2) return false;
    	for(int i = 2; i <= n / i; i++) { 
    		if(n % i == 0) return false;
    	}
    	return true;
    }
    
    int main() { 
    	int m;
    	scanf("%d", &m);
    	while(m--) { 
    		int a;
    		scanf("%d", &a);
    		if(is_prime(a)) printf("Yes\n");
    		else printf("No\n");
    	}
    	return 0;
    }

#### 分解质因数 ####

##### 朴素思路 #####

还是采用试除法。

对于一个数`N`，总能够写成如下的式子：

N = P 1 k 1 × P 2 k 2 × . . . . . . P n k n N = P\_1^\{k\_1\} × P\_2^\{k\_2\} × ......P\_n^\{k\_n\} N=P1k1×P2k2×......Pnkn，其中 P 1 P\_1 P1到 P n P\_n Pn皆是质数， k 1 k\_1 k1 到  k n k\_n kn 都是大于0的正整数。

对于一个数 n n n 求解质因数的过程如下：

**从2到n，枚举所有数，依次判断是否能够整除 n 即可**。

这里可能有个疑问，不是应当枚举所有的质数吗？怎么是枚举所有数？枚举所有数如果取到合数怎么办？那分解出来的就不是质因子了啊。

下面进行一下解释：

我们枚举数时，对于每个能整除`n`的数，**先把这个数除干净了**，再继续枚举后面的数，这样能保证，后续再遇到能整除的数，一定是质数而不是合数。

除干净是什么意思呢？比如 n=24，我们先枚举2，发现2能整除24，则除之，24÷2=12，得到的结果是12，发现2仍然能整除之，则除之，12÷2=6，仍能整除，除之！6÷2=3。2不能整除3了。则停止。继续枚举下一个数3，3÷3=1。

质因数分解结束。则 24 = 2 3 × 3 1 24=2^3×3^1 24=23×31，24的质因子就有两个，分别是2和3。

那么，把一个数除干净了，怎么就能保证后续遇到能整除的数一定是质数了呢？

假设后续枚举到一个合数`k`，这个合数能整除`n`，则这个合数的某个质因子`p`，也能整除n。就比如合数6能整除24，则6的质因子2，肯定也能整除24。

合数`k`的质因子`p`一定比合数本身小，而我们是从小到大进行枚举，则`p`一定在`k`之前被枚举过了，而之前枚举`p`时，是把`p`除干净了的，此时不应当还能被`p`整除，这就矛盾了。所以在枚举时，如果遇到能整除的数，只可能是质数，而不可能是合数。（我们是从2开始枚举的，而2是一个质数）

void divide(int n) { 
        for(int i = 2; i <= n; i++) { 
            if(n % i == 0) { 
                int s = 0;
                while(n % i == 0) { 
                    s++;
                    n /= i;
                }
                printf("%d %d\n", i, s);
            }
        }
    }

##### 优化 #####

从2枚举到n，时间复杂度就是O(n)。其实不必枚举到n。下面进行一下优化

**有一个重要性质**： n n n 中最多只包含一个大于 n \\sqrt\{n\} n 的质因子

这个结论很好证明，因为我们知道一个数 n n n 分解质因数后可以写成

n = P 1 k 1 × P 2 k 2 × . . . . . . P n k n n = P\_1^\{k\_1\} × P\_2^\{k\_2\} × ......P\_n^\{k\_n\} n=P1k1×P2k2×......Pnkn

其中 P 1 P\_1 P1 到  P n P\_n Pn 都是  n n n 的质因子，若存在两个大于 n \\sqrt\{n\} n 的质因子，就算两个质因子的指数都是最小的1，这两个质因子乘起来也大于  n n n 了，于是就矛盾了。

所以我们只用枚举到  n \\sqrt\{n\} n 即可，即枚举的  i i i 一定满足  i ≤ n i \\le \\sqrt\{n\} i≤n，即  i ≤ n i i \\le \\frac\{n\}\{i\} i≤in

优化后的求解质因子的代码如下（时间复杂度为  O ( n ) O(\\sqrt\{n\}) O(n)）

void divide(int n) { 
        for(int i = 2; i <= n / i; i++) { 
            if(n % i == 0) { 
                int s = 0;
                while(n % i == 0) { 
                    s++;
                    n /= i;
                }
                printf("%d %d\n", i, s);
            }
        }
        // 如果除完之后, n是大于1的, 
        // 说明此时的n就是那个大于 原根号n 的最大的质因子, 单独输出一下
        if(n > 1) printf("%d %d\n", n, 1);
    }

注意枚举完毕后，如果最终的n不等于1，则最后剩下的这个n，就是最大的一个质因子（大于原来的  n \\sqrt\{n\} n 的那个质因子），需要单独输出一下。

比如 n=39，由于枚举时的条件是  i ≤ n i i \\le \\frac\{n\}\{i\} i≤in ，则只会枚举到6，for循环就结束了，而39有一个质因子是13

练习题：[acwing - 867: 分解质因数][acwing - 867_]

#include<iostream>
    using namespace std;
    
    void divide(int n) { 
    	for(int i = 2; i <= n / i; i++) { 
    		if(n % i == 0) { 
    			int s = 0;
    			while(n % i == 0) { 
    				s++;
    				n /= i;
    			}
    			printf("%d %d\n", i, s);
    		}
    	}
    	if(n > 1) printf("%d %d\n", n, 1);
    }
    
    int main() { 
    	int m;
    	scanf("%d", &m);
    	while(m--) { 
    		int a;
    		scanf("%d", &a);
    		divide(a);
    		printf("\n");
    	}
    	return 0;
    }

#### 筛选质数 ####

练习题：[acwing - 868: 筛质数][acwing - 868_]

对于一个数n，求解1~n中质数的个数

##### 朴素筛法 #####

将2到n全部数放在一个集合中，**遍历2到n，删除集合中这个数的倍数**。最后集合中剩下的数就是质数。

解释：如果一个数`p`没有被删掉，那么说明在2到`p-1`之间的所有数，`p`都不是其倍数，即2到`p-1`之间，不存在`p`的约数。故`p`一定是质数。

时间复杂度：

n 2 + n 3 + . . . . + n n = n ( 1 2 + 1 3 + . . . . + 1 n ) = n ln ⁡ n \\frac\{n\}\{2\}+\\frac\{n\}\{3\}+....+\\frac\{n\}\{n\} = n(\\frac\{1\}\{2\} + \\frac\{1\}\{3\} + ....+\\frac\{1\}\{n\})=n\\ln n 2n\+3n\+....\+nn=n(21\+31\+....\+n1)=nlnn

而 n ln ⁡ n = n log ⁡ e n n\\ln n = n\\log\_en nlnn=nlogen，而 e = 2.71828 e=2.71828 e=2.71828左右，是大于2的，所以 n ln ⁡ n < n l o g 2 n n\\ln n \\lt nlog\_2n nlnn<nlog2n

故，朴素思路筛选质数的时间复杂度大约为  O ( n l o g 2 n ) O(nlog\_2n) O(nlog2n)

#include<iostream>
    using namespace std;
    
    const int N = 1e6 + 10;
    
    int ctn;
    
    bool st[N];
    
    void get_primes(int n) { 
    	for(int i = 2; i <= n; i++) { 
    		if(!st[i]) ctn++; // i是质数
    		for(int j = i; j <= n; j += i) st[j] = true; // 删数
    	}
    }
    
    int main() { 
    	int n;
    	scanf("%d", &n);
    	get_primes(n);
    	printf("%d", ctn);
    }

其实上面的代码的运行过程不是完全按照朴素思路所描述的那样。上面的代码用一个布尔数组来表示一个数是否被删除。

遍历2到n，对每个数，先看一下其是否被删除了，若没有，则说明其是一个质数，随后将这个数以及其倍数全部删除（布尔数组置为`true`）。每当遍历到一个数时，如果这个数没有被前面的数所删掉，则说明这个数是个质数。

##### 埃氏筛法 #####

其实不需要把全部数的倍数删掉，而只需要删除质数的倍数即可。

对于一个数`p`，判断其是否是质数，其实不需要把`2`到`p-1`全部数的倍数删一遍，只要删掉`2`到`p-1`之间的质数的倍数即可。因为，若`p`不是个质数，则其在`2`到`p-1`之间，一定有质因数，只需要删除其质因数的倍数，则`p`就能够被删掉。优化后的代码如下

#include<iostream>
    using namespace std;
    
    const int N = 1e6 + 10;
    
    int ctn;
    
    bool st[N];
    
    void get_primes(int n) { 
    	for(int i = 2; i <= n; i++) { 
    		if(!st[i]) { 
    			ctn++;
    			for(int j = i; j <= n; j += i) st[j] = true;
    		}
    	}
    }
    
    int main() { 
    	int n;
    	scanf("%d", &n);
    	get_primes(n);
    	printf("%d", ctn);
    }

那么优化后的时间复杂度如何呢？

原本我们需要对每个数都删掉其倍数，现在只需要对是质数的数，删掉其倍数。需要操作的数的个数明显减少了很多。要估算优化后的算法的时间复杂度，问题是，质数的个数究竟有多少个呢？

根据质数定理，在1到n之间，质数的个数大约为  n ln ⁡ n \\frac\{n\}\{\\ln n\} lnnn，我们原本需要对n个数进行操作，现在只需要对 n ln ⁡ n \\frac\{n\}\{\\ln n\} lnnn个数进行操作，所以时间复杂度就除以个 ln ⁡ n \\ln n lnn（其实这样算是不正确的），即 n ln ⁡ n ÷ ln ⁡ n = n n\\ln n \\div \\ln n = n nlnn÷lnn=n，所以优化后的算法的时间复杂度大约是  O ( n ) O(n) O(n)，其实准确复杂度是 n log ⁡ log ⁡ n n\\log\{\\log n\} nloglogn。

这种优化后的筛选质数的方法，被称为**埃氏筛法**（埃拉托斯特尼筛法）。

##### 线性筛法 #####

下面多介绍一种**线性筛法**，其性能要优于**埃氏筛法**（在106 下两个算法差不多，在107下线性筛法大概快一倍），其思想也类似，把每个合数，用它的某一个质因子删掉就可以了。

核心思路是：**对于某一个合数n，其只会被自己的最小质因子给筛掉。**

先上一下代码

#include<iostream>
    using namespace std;
    
    const int N = 1e6 + 10;
    
    int ctn;
    
    int primes[N];
    
    bool st[N];
    
    void get_primes(int n) { 
    	for(int i = 2; i <= n; i++) { 
    		if(!st[i]) primes[ctn++] = i;
    		for(int j = 0; primes[j] <= n / i; j++) { 
    			st[primes[j] * i] = true;
                // 当下面的if条件成立时, primes[j]一定是i的最小质因子
    			if(i % primes[j] == 0) break;
    		}
    	}
    }
    
    int main() { 
    	int n;
    	scanf("%d", &n);
    	get_primes(n);
    	printf("%d", ctn);
    }

对上面的代码解释如下：

用  p j pj pj 来表示`primes[j]`

*  当 i % p j = 0 i \\% pj = 0 i%pj=0时
    
     p j pj pj一定是  i i i 的最小质因子，因为我们是从小到大枚举质数的，首先遇到的满足 i % p j = 0 i \\% pj = 0 i%pj=0的， p j pj pj一定是  i i i 的最小质因子，
    
    **并且**  p j pj pj 一定是  p j × i pj \\times i pj×i 的最小质因子。
    
    这么说可能不太好理解，假设4的最小质因子为2，写成分解质因数的形式，即为  4 = 2 2 4=2^2 4=22。
    
    则，4的倍数中最小的数，且最小质因子同样是2的，一定是给4本身，再乘以一个其最小质因子，得到的数，即8。
    
    再举个例子， 15 = 3 × 5 15 = 3 \\times 5 15=3×5，15的最小质因子是3，则15的倍数中最小的数，且最小质因子同样是3的，一定是给15乘以一个最小质因子3，即45。
 *  当  i % p j ≠ 0 i \\% pj \\ne 0 i%pj=0 时
    
     p j pj pj 一定不是 i i i 的质因子。并且由于是从小到大枚举质数的，那么  p j pj pj 一定小于  i i i 的全部质因子。那么 p j pj pj 就一定是  p j × i pj \\times i pj×i 的最小质因子。

则无论哪种情况， p j pj pj 都一定是  p j × i pj \\times i pj×i 的最小质因子。

那么线性筛法是如何保证，所有的合数都一定能被删掉呢？ 假设，有一个合数  x x x，那么其一定有一个最小质因子  p j pj pj，那么当枚举到  i = x p j i = \\frac\{x\}\{pj\} i=pjx 的时候，就能把  x x x 删掉

线性筛法保证了，每个合数，都是被其最小质因子给删掉的，且只会被删一次

运行时间如下

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70][]

从上往下依次是**线性筛法**，**埃氏筛法**，**朴素筛法**。

##### 小结 #####

三种筛选质数的方法，都是基于删除数来完成的，我们只要删除合数，剩下的就是质数了。由于质数的约数只有1和它本身，而合数一定存在其他约数。先想一个比较朴素的暴力做法，那么就是枚举2到n，依次删除每个数的倍数，那么n以内的全部合数就被删除完毕，剩下的数就是质数。

用动图表示如下（动图来源于知乎，原链接[在此][Link 1]）

![f18fc53e0d76eba142d72d4f62867293.gif][]

**朴素筛法**代码如下

void get_primes(int n) { 
    	for(int i = 2; i <= n; i++) { 
    		if(!st[i]) ctn++; // i是质数
    		for(int j = i; j <= n; j += i) st[j] = true; // 删数
    	}
    }

随后，反观这个过程，我们考虑如何进行优化。

首先，暴力做法枚举了2到n全部的数，它做的无用功主要有

1.  枚举的过程中，有些后面的数已经被前面的数的倍数给删掉了，但也会枚举到
    
    比如4，在枚举2的时候已经被删除了，但还是会被枚举到
2.  删除时，有的数已经被前面的数删了，但还可能会被后面的数再删一次
    
    比如6，在枚举2时已经被删除了，但在枚举3时还会被再删一次

针对1，没什么好优化的，因为在算法执行过程中，被删除的数是动态变化的，我们并不能预先确定哪些数不需要枚举。

优化主要针对2。我们的目的是删除合数，做法是通过删除一个数的倍数来完成。因为每个合数都能够分解质因数，合数一定是某个质数的倍数。所以，我们其实不需要删除所有数的倍数，**只需要删除所有质数的倍数，即可删除所有合数**。

故可对朴素筛法进行优化，仅当枚举到的是质数时，才执行删除。这便是**埃氏筛法**，代码如下

void get_primes(int n) { 
    	for(int i = 2; i <= n; i++) { 
    		if(!st[i]) { 
    			ctn++; // i 是质数
    			for(int j = i; j <= n; j += i) st[j] = true; // 删除这个质数的倍数
    		}
    	}
    }

埃氏筛法能优化算法性能，但还不是最优。我们考虑6这个合数，它会被质数2删除一次，还会被质数3再删除一次。

于是，我们接着想，删除一个合数，其实只需要**删除这个合数的最小质因子的倍数**即可。比如6有两个质因子，2和3，其实只需要用2来删除即可。这便是**线性筛法**。线性筛法需要记录质数，故需要开一个额外的数组来存质数。其代码如下

void get_primes(int n) { 
        for(int i = 2; i <= n; i++) { 
            if(!st[i]) primes[ctn++] = i; // i 是质数
            for(int j = 0; primes[j] <= n / i; j++) { 
                st[primes[j] * i] = true;
                if(i % primes[j] == 0) break;
            }
        }
    }

线性筛法的思想很简单：对每个合数，都用其最小质因子的倍数来删掉它。但是代码理解起来不是很容易。下面进行一个说明

首先从2到n，枚举每个数，用  i i i 表示当前枚举的数，边枚举边保存得到的质数，则  p r i m e s primes primes 数组中保存的是小于等于  i i i 的全部质数。

在每次枚举  i i i 时，尝试枚举小于  i i i 的全部质数，即尝试枚举全部的  p r i m e s primes primes 数组，并尝试删除  p r i m e s j × i primes\_j \\times i primesj×i

需要保证  p r i m e s j × i primes\_j \\times i primesj×i 小于等于  n n n ，因为我们求的是  n n n 以内的质数，删除合数只需要删除小于  n n n 的合数即可，否则会导致  s t st st 数组越界。

每次从最小的质数开始枚举，删除  p r i m e s j × i primes\_j \\times i primesj×i。因为，无论  p r i m e s j primes\_j primesj 能否整除  i i i，都能保证  p r i m e s j primes\_j primesj 一定是  p r i m e s j × i primes\_j \\times i primesj×i 的最小质因子。

而当  i % p r i m e s j = 0 i \\% primes\_j = 0 i%primesj=0 时，退出循环。

为什么在  i % p r i m e s j = 0 i \\% primes\_j = 0 i%primesj=0 时要退出呢？这是为了保证，每个合数都被其最小质因子给删掉，且只删一次。

假设在  i % p r i m e s j = 0 i \\% primes\_j = 0 i%primesj=0 时不退出循环，则下一轮会枚举到下一个质数  p r i m e s j + 1 primes\_\{j+1\} primesj\+1 ，此时会删除  p r i m e s j + 1 × i primes\_\{j+1\} \\times i primesj\+1×i ，且是用的  p r i m e s j + 1 primes\_\{j+1\} primesj\+1 去删除的，但  p r i m e s j + 1 × i primes\_\{j+1\} \\times i primesj\+1×i 的最小质因子应该是  p r i m e s j primes\_j primesj，因为  i % p r i m e s j = 0 i \\% primes\_j = 0 i%primesj=0 。而对于每个合数，我们应当用其最小质因子来删掉它。所以这里需要`break`。

并且，如果不`break`的话，下一轮`j++`可能导致  p r i m e s primes primes 数组越界。

其实，在  i % p r i m e s j = 0 i \\% primes\_j = 0 i%primesj=0 时也可以不`break`，但是为了防止`j`越界，此时应当在循环条件中加上  j < c t n j \\lt ctn j<ctn ，这样才能保证算法正确性。但是如此以来，会导致一个合数被删除多次，所以其性能会有所降低，并不能算是线性筛法。

如果在  i % p r i m e s j = 0 i \\% primes\_j = 0 i%primesj=0 时 `break` 了，则能保证每个合数都只被删除一次，且都是被其最小质因子删除的。并且也能保证枚举  p r i m e s primes primes 数组时， j j j 不会越界。因为  p r i m e s primes primes 数组存储的是小于等于  i i i 的所有质数，

若  i i i 是合数，则一定存在一个小于  i i i 的质数，能够整除  i i i，则一定会在  j j j 越界前`break`掉；

若  i i i 是质数，那么  i i i 一定是当前  p r i m e s primes primes 数组中的最后一个数，则在  j j j 的最后一个位置一定会有  p r i m e s j = i primes\_j = i primesj=i，所以  j j j 也不会越界。

### 约数 ###

#### 求一个数的所有约数 ####

试除法求一个数的所有约数，和试除法判断质数的思路一样

练习题：[acwing - 869: 试除法求约数][acwing - 869_]

#include<iostream>
    using namespace std;
    const int N = 2e8 + 10;
    
    int l[N], h[N];
    
    void get_dividers(int n) { 
    	// 只枚举较小的约数即可
    	int lctn = 0, hctn = 0;
    	for(int i = 1; i <= n / i; i++) { 
    		if(n % i == 0) { 
    			l[lctn++] = i;
    			if(i != n / i) h[hctn++] = n / i; // 重复约数需要排除
    		}
    	}
    	for(int i = 0; i < lctn; i++) printf("%d ", l[i]);
    	for(int i = hctn - 1; i >= 0; i--) printf("%d ", h[i]);
    	printf("\n");
    }
    
    int main() { 
    	int m;
    	scanf("%d", &m);
    	while(m--) { 
    		int n;
    		scanf("%d", &n);
    		get_dividers(n);
    	}
    	return 0;
    }

#### 求约数个数 ####

假设一个数  N N N ，其分解质因数可写成  N = P 1 k 1 × P 2 k 2 × . . . . . . P n k n N = P\_1^\{k\_1\} × P\_2^\{k\_2\} × ......P\_n^\{k\_n\} N=P1k1×P2k2×......Pnkn

则  N N N 的约数个数为  ( k 1 + 1 ) × ( k 2 + 1 ) × . . . . × ( k n + 1 ) (k\_1+1) \\times (k\_2+1) \\times .... \\times (k\_n+1) (k1\+1)×(k2\+1)×....×(kn\+1)

其实就是排列组合。

对于  N N N 的每个质因子，我们在构造一个约数时，可以选择是否将其纳入。

比如对于质因子  P 1 P\_1 P1，它的指数是  k 1 k\_1 k1，则我们有  k 1 + 1 k\_1+1 k1\+1 种选择，即：纳入  0 0 0 个  P 1 P\_1 P1，纳入  1 1 1 个  P 1 P\_1 P1，…，纳入  k 1 k\_1 k1 个  P 1 P\_1 P1，对于质因子  P 2 P\_2 P2 同理。

当所有的质因子我们都不纳入时，得到的约数就是  1 1 1，当所有的质因子我们全纳入时（每个质因子的指数取最大），得到的约数就是  N N N 本身。

一共有多少种组合方式呢？

对于每个质因子  P i P\_i Pi 我们都有  k i + 1 k\_i + 1 ki\+1 种选择，总共的组合方式就是将每个质因子的选择数相乘，即得到上面的公式。

在`int`范围内的全部数，约数个数最多的一个数，其约数个数大概有1500个

练习题：[acwing - 870: 约数个数][acwing - 870_]

#include<iostream>
    #include<unordered_map>
    using namespace std;
    
    typedef long long LL;
    
    const int N = 1e9 + 7;
    
    int main() { 
    	int m;
    	scanf("%d", &m);
    	unordered_map<int, int> primes; // 计数所有的质因子及其指数
    	while(m--) { 
    		int n;
    		scanf("%d", &n);
    		for(int i = 2; i <= n / i; i++) { 
    			while(n % i == 0) { 
    				n /= i;
    				primes[i]++;
    			}
    		}
    		if(n > 1) primes[n]++;
    	}
    	unordered_map<int, int>::iterator it = primes.begin();
    	LL res = 1;
    	while(it != primes.end()) { 
    		res = (res * (it->second + 1)) % N;
    		it++;
    	}
    	printf("%lld", res);
    	return 0;
    }

#### 求约数之和 ####

数  N N N 的所有约数之和等于

( P 1 0 + P 1 1 + . . . + P 1 k 1 ) × . . . . . × ( P n 0 + P n 1 + . . . + P n k n ) (P\_1^0+P\_1^1+...+P\_1^\{k\_1\}) \\times ..... \\times (P\_n^0+P\_n^1+...+P\_n^\{k\_n\}) (P10\+P11\+...\+P1k1)×.....×(Pn0\+Pn1\+...\+Pnkn)

将上面的式子按照乘法分配律展开，会得到如下的形式

( . . × . . ) + ( . . × . . ) + ( . . × . . ) + . . . (.. \\times ..) + (.. \\times ..) + (.. \\times ..) + ... (..×..)\+(..×..)\+(..×..)\+...

每一项都是一个乘积，而这个乘积，就是从每个  P i P\_i Pi 中选择了一项，互相乘了起来，这一个乘积就是  N N N 的一个约数。

练习题：[acwing - 871: 约数之和][acwing - 871_]

#include<iostream>
    #include<unordered_map>
    using namespace std;
    
    const int N = 1e9 + 7;
    
    typedef long long LL;
    
    int main() { 
    	int m;
    	scanf("%d", &m);
    	unordered_map<int, int> primes;
    	while(m--) { 
    		int n;
    		scanf("%d", &n);
    		for(int i = 2; i <= n / i; i++) { 
    			while(n % i == 0) { 
    				primes[i]++;
    				n /= i;
    			}
    		}
    		if(n > 1) primes[n]++;
    	}
    	LL res = 1;
    	for(auto p : primes) { 
    		int a = p.first, b = p.second; // 质因数的底数和指数
    		LL t = 1;
    		for(int i = 0; i < b; i++) { 
    			t = (t * a + 1) % N;
    		}
    		res = (res * t) % N;
    	}
    	printf("%lld", res);
    	return 0;
    }

#### 求最大公约数 ####

欧几里得算法（辗转相除法）

我们用 g c d ( a , b ) gcd(a,b) gcd(a,b) 来表示  a a a 和  b b b 的最大公约数，有如下公式

g c d ( a , b ) = g c d ( b , a m o d    b ) gcd(a,b) = gcd(b, a \\mod b) gcd(a,b)=gcd(b,amodb)

*  当 a m o d    b = 0 a \\mod b = 0 amodb=0 时，最大公约数是  b b b
 *  否则，最大公约数就是  b b b 和  a m o d    b a \\mod b amodb 的最大公约数

比如，求解 g c d ( 42 , 12 ) gcd(42,12) gcd(42,12)，由于  a m o d    b ≠ 0 a \\mod b \\ne 0 amodb=0，则求解  g c d ( 12 , 42 m o d    12 ) = g c d ( 12 , 6 ) gcd(12, 42 \\mod 12) = gcd(12,6) gcd(12,42mod12)=gcd(12,6)，而  g c d ( 12 , 6 ) gcd(12,6) gcd(12,6) 发现  6 6 6 能整除  12 12 12，则最大公约数就是  6 6 6

对上述算法的正确性，证明如下：

假设  a a a 和  b b b 的最大公约数是  k k k ，则  a = k × a k a = k \\times a\_k a=k×ak， b = k × b k b = k \\times b\_k b=k×bk，由于  k k k 是最大的公约数，则容易得知  a k a\_k ak 和  b k b\_k bk 一定是互质的（若不互质的话， a k a\_k ak 和  b k b\_k bk 一定存在一个大于1的公约数，可以将这个约数乘到  k k k 上，这样就使得  a a a 和  b b b 的最大公约数不是  k k k 了，而是  k k k 的某个倍数）。

由于公式中需要  a m o d    b a \\mod b amodb，所以我们将  a a a 写成  a = c × b + d a = c \\times b + d a=c×b\+d，将  c × b + d c \\times b + d c×b\+d 中的  b b b 用  k × b k k \\times b\_k k×bk 替换，得到  k × b k × c + d k \\times b\_k \\times c + d k×bk×c\+d

即  k × b k × c + d = k × a k k \\times b\_k \\times c + d = k \\times a\_k k×bk×c\+d=k×ak，在等式左半边的部分将  k k k 提取出来

即  k × （ b k × c + d k ） = k × a k k \\times （b\_k \\times c + \\frac\{d\}\{k\}） = k \\times a\_k k×（bk×c\+kd）=k×ak，消掉  k k k，得  b k × c + d k = a k b\_k \\times c + \\frac\{d\}\{k\} = a\_k bk×c\+kd=ak

由于  a k a\_k ak 是个整数，则  b k × c + d k b\_k \\times c + \\frac\{d\}\{k\} bk×c\+kd 一定是个整数，即  d k \\frac\{d\}\{k\} kd 一定是整数 ，  d d d 一定是  k k k 的倍数，即  d = d k × k d = d\_k \\times k d=dk×k。

由于  d = a m o d    b d = a \\mod b d=amodb，于是，我们推导出了， a m o d    b a \\mod b amodb 一定是  a a a 和  b b b 的最大公约数  k k k 的倍数。由于我们的公式是  g c d ( a , b ) = g c d ( b , a m o d    b ) gcd(a,b)=gcd(b, a \\mod b) gcd(a,b)=gcd(b,amodb)，那还存在一个问题，虽然  d d d 也是  k k k 的倍数，但  b b b 和  d d d 的最大公约数一定就是  k k k 吗？也就是说， g c d ( b , a m o d    b ) gcd(b, a \\mod b) gcd(b,amodb) 的答案一定等价于  g c d ( a , b ) gcd(a,b) gcd(a,b) 吗？这是一定的。下面采用反证法进行说明。

若  d d d 和  b b b 的最大公约数大于  k k k ，假设为  k p l u s k\_\{plus\} kplus ，则有 b = b k p × k p l u s b = b\_\{kp\} \\times k\_\{plus\} b=bkp×kplus， d = d k p × k p l u s d=d\_\{kp\} \\times k\_\{plus\} d=dkp×kplus，将这两项带入到  a = c × b + d a = c \\times b + d a=c×b\+d 当中，有  a = c × b k p × k p l u s + d k p × k p l u s a = c \\times b\_\{kp\} \\times k\_\{plus\} + d\_\{kp\} \\times k\_\{plus\} a=c×bkp×kplus\+dkp×kplus，可以将  k p l u s k\_\{plus\} kplus 提取出来，则说明  a a a 有一个大于  k k k 的约数  k p l u s k\_\{plus\} kplus ，而  k p l u s k\_\{plus\} kplus 同时也是  b b b 的约数，则  a a a 和  b b b 存在一个大于  k k k 的约数  k p l u s k\_\{plus\} kplus ，这与  k k k 是  a a a 和  b b b 的最大公约数矛盾了。所以， b b b 和  d d d 的最大公约数一定是  k k k 。

所以求解  k k k，就相当于求解  b b b 和  d d d 的最大公约数，即相当于求  b b b 和  a m o d    b a \\mod b amodb 的最大公约数。

在编写代码时，一开始会考虑到， g c d ( a , b ) = g c d ( b , a m o d    b ) gcd(a,b) = gcd(b, a \\mod b) gcd(a,b)=gcd(b,amodb) ，是否需要注意  a a a 和  b b b 的大小位置关系（是否一定需要保证  a > b a \\gt b a>b 呢？），实际发现不用。

举例如下

假设求解  12 12 12 和  30 30 30 的最大公约数，如果我们写成  g c d ( 12 , 30 ) gcd(12, 30) gcd(12,30)

则  g c d ( 12 , 30 ) = g c d ( 30 , 12 m o d    30 ) = g c d ( 30 , 12 ) gcd(12,30) = gcd(30, 12 \\mod 30) = gcd(30, 12) gcd(12,30)=gcd(30,12mod30)=gcd(30,12)，会自动调整好顺序，使得  a > b a \\gt b a>b ，只是多一层递归而已。

随后便是  g c d ( 30 , 12 ) = g c d ( 12 , 6 ) = 6 gcd(30,12) = gcd(12, 6) = 6 gcd(30,12)=gcd(12,6)=6

练习题：[acwing - 872: 最大公约数][acwing - 872_]

#include<iostream>
    using namespace std;
    
    // 写代码时可以假设一定满足 a > b 
    // 就算 a < b , 也会在第一次递归时调转位置
    int gcd(int a, int b) { 
        // b == 0 时, 直接返回a, 否则进行辗转相除
        return b ? gcd(b, a % b) : a;
    }
    
    int main() { 
        int m;
        scanf("%d", &m);
        while(m--) { 
            int a, b;
            scanf("%d%d", &a, &b);
            printf("%d\n", gcd(a, b));
        }
        return 0;
    }

(已于2021/07/23 更新，更新内容为校正了辗转相除法求最大公约数的推导过程)

[acwing - 866_]: https://www.acwing.com/problem/content/submission/868/
[acwing - 867_]: https://www.acwing.com/problem/content/869/
[acwing - 868_]: https://www.acwing.com/problem/content/870/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70]: /images/20221004/8a8efca9b78a4d53b738350d28253746.png
[Link 1]: https://zhuanlan.zhihu.com/p/124068032?utm_source=qq
[f18fc53e0d76eba142d72d4f62867293.gif]: /images/20221004/c35e9d2f28994a4ab23ebe8f7a95e38b.png
[acwing - 869_]: https://www.acwing.com/problem/content/871/
[acwing - 870_]: https://www.acwing.com/problem/content/872/
[acwing - 871_]: https://www.acwing.com/problem/content/description/873/
[acwing - 872_]: https://www.acwing.com/problem/content/874/