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

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

@@ 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$的所有约数。

数据范围

$1\le n\le 100$,

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

思路

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

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

这题的时间复杂度是$O(n\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$取模。

数据范围

$1\le n\le 100$,

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

思路

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

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

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

数学上，这可以表达为：

$N=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,\dots ,a_n$ 是正整数。这种分解称为 $N$ 的标准分解式。

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

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

例如：

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

证明方法简述：

1. 存在性证明：

   • 假设存在某个大于1的自然数不能写成质数的乘积。
   • 选择所有这样的数中最小的那个，设为 $n$。
   • 由于 $n$ 不是质数，它可以分解为两个小于 $n$ 的自然数的乘积。
   • 但这两个数都可以写成质数的乘积（因为它们都小于 $n$，且假设中不存在不能分解为质数乘积的数）。
   • 因此，$n$ 也可以写成质数的乘积，与假设矛盾。

2. 唯一性证明：

   • 假设存在某个大于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$取模。

数据范围

$1\le n\le 100$,

$2\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;
}