数据结构与算法学习笔记----约数

@@ author: 明月清了个风
@@ first publish time: 2024.12.30

ps⭐️主要是求约数，约数的个数，约数的和，涉及到算术基本定理的相关内容，第三题的讲解合并在第二题的思路里一起了。

Acwing 869. 试除法求约数

[原题链接](869. 试除法求约数 - AcWing题库)

给定 $n$ 个正整数 $a_i$ ，对于每个整数 $a_i$ ，请你按照从小到大的顺序输出它的所有约数

输入格式

第一行包含整数 $n$ ，

接下来 $n$ 行，每行包含一个正整数 $a_i$ 。

输出格式

输出 $n$ 行，其中每 $i$ 行输出第 $i$ 个整数 $a_i$ 的所有约数。

数据范围

$\le n \le 100$ ,

$\le a_i \le 2\times 10^9$

思路

试除法和质数中是一样的，只是我们统计的量不一样了

需要注意的就是时间复杂度了，数论中的题目需要注意时间复杂度，这关系到我们要使用什么方法解决

这题的时间复杂度是 $\times \sqrt{a})$ ， $a$ 的范围如题，因此可以得到整体时间复杂度大概在400万~500万。

代码

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>using namespace std;vector<int> get_dividers(int n)
{vector<int> res;for(int i = 1; i <= n / i; i ++){if(n % i == 0){res.push_back(i);if(i != n / i) res.push_back(n / i);}}sort(res.begin(), res.end());return res;
}int main()
{int n;cin >> n;while(n --){int x;cin >> x;vector<int> ans = get_dividers(x);for(auto t : ans) cout << t << ' ';cout << endl;}return 0;    
}

Acwing 870. 约数个数

[原题链接](870. 约数个数 - AcWing题库)

给定 $n$ 个正整数 $a_i$ ，请你输出这些数的乘积的约数个数，答案对 $10^9 + 7$ 取模。

输入格式

第一行包含整数 $n$ ，

接下来 $n$ 行，每行包含一个正整数 $a_i$ 。

输出格式

输出一个整数，表示所给正整数的乘积的约数个数，答案需对 $10^9 + 7$ 取模。

数据范围

$\le n \le 100$ ,

$\le a_i \le 2 \times 10^9$

思路

这里就要用到算术基本定理（这个定理的相关内容从下面的红字开始，若想跳过直接往下看蓝字）了。

算术基本定理，又称为正整数的唯一分解定理，是初等数论中一个非常重要的定理。它揭示了整数的基本性质，具体表述为：

任何一个大于1的自然数，如果不为质数，那么它可以唯一分解成有限个质数的乘积。

数学上，这可以表达为：

$p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3} \times \cdots \times p_n^{a_n}$

其中， $p_1 < p_2 < p_3 < \cdots < p_n$ 均为质数， $a_1, a_2, a_3, \ldots, a_n$ 是正整数。这种分解称为 $N$ 的标准分解式。

算术基本定理包含两个核心要点：

存在性：每个大于1的自然数都可以写成质数的乘积。
唯一性：这种分解方式是唯一的，即不考虑质数的排列顺序，每个大于1的自然数只有一种质因数分解方式。

例如：

数字 $60$ 可以唯一分解为 $2^2 \times 3 \times 5$ 。
数字 $825$ 可以唯一分解为 $\times 5^2 \times 11$ 。

证明方法简述：

存在性证明：
- 假设存在某个大于1的自然数不能写成质数的乘积。
- 选择所有这样的数中最小的那个，设为 $n$ 。
- 由于 $n$ 不是质数，它可以分解为两个小于 $n$ 的自然数的乘积。
- 但这两个数都可以写成质数的乘积（因为它们都小于 $n$ ，且假设中不存在不能分解为质数乘积的数）。
- 因此， $n$ 也可以写成质数的乘积，与假设矛盾。
唯一性证明：
- 假设存在某个大于1的自然数可以以多于一种的方式写成质数的乘积。
- 选择所有这样的数中最小的那个，设为 $n$ 。
- 将 $n$ 的两种分解式中的质数进行比较，利用反证法和欧几里得引理（若质数 $p$ 能整除两数之积，则必能整除其中至少一个数）推导出矛盾。

上面是算术基本定理的相关内容，重新回到题目中，对于每个数 $a_i$ ，我们都可以进行这样的分解，那么每个数的约数的个数就可以看着所有质因数 $p_i^{a_i}$ 的排列组合，因此约数的个数就可以得到为 $(a_1 + 1)(a_2 + 1)\cdots(a_n + 1)$ 。

这里还有个小知识点，int范围内约数个数最多的整数大概有1500个约数。

这里就直接将下一题的约数之和的算法讲了。

约数之和为 $({p_1}^0+ {p_1}^1+ \cdots + {p_1}^{a_1}) \cdots ({p_n}^0+ {p_n}^1+ \cdots + {p_n}^{a_n})$ ，这应该也很好理解，这个多项式乘法的展开就是在每个括号中取一项乘起来，那么每个括号中的取法就有 $a_i + 1)$ 种，所以最后一共有 $(a_1 + 1)(a_2 + 1)\cdots(a_n + 1)$ 项，即约数的个数，将这些项全部相加，即为约数之和。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <unordered_map>using namespace std;typedef long long LL;const int 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 prime : primes) res = res * (prime.second + 1) % mod;cout << res << endl;return 0;
}

Acwing 871. 约数之和

[原题链接](871. 约数之和 - AcWing题库)

给定 $n$ 个正整数 $a_i$ ，请你输出这些数的乘积的约数之和，答案对 $10^9 + 7$ 取模。

输入格式

第一行包含整数 $n$ ，

接下来 $n$ 行，每行包含一个正整数 $a_i$ 。

输出格式

输出一个整数，表示所给正整数的乘积的约数之和，答案需对 $10^9 + 7$ 取模。

数据范围

$\le n \le 100$ ,

$\le a_i \le 2 \times 10^9$

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <unordered_map>using namespace std;typedef long long LL;const int 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 prime : primes){int a = prime.first, b = prime.second;LL t = 1;while(b --) t = (t * a + 1) % mod;res = res * t % mod;}cout << res << endl;return 0;
}