算法基础课笔记（三五）

7.2：约数

约数也称为因数。

例题：869. 试除法求约数（模板题）

试除法求约数，原理类似试除法求质数。约数也是成对出现的，所以只需要枚举[2,sqrt(n)]。

试除法时间复杂度：$O(\sqrt n)$。

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

输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。

输出格式
输出共 n 行，其中第 i 行输出第 i 个整数 ai 的所有约数。

数据范围
1≤n≤100,
2≤ai≤2×10^9
输入样例：
2
6
8
输出样例：
1 2 3 6
1 2 4 8

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> get_divisors(int x){
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ ){ // 约数从1开始枚举
        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,x;
    cin >> n;
    while (n -- ){
        cin >> x;
        auto res = get_divisors(x);
        for (int &it:res) cout << it << ' ';
        cout << '\n';
    }
    return 0;
}

数论题中很重要的一点就是计算时间复杂度。

本题时间复杂度是$O(n*\sqrt a)$。

例题：870. 约数个数（模板题）

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

输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。

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

数据范围
1≤n≤100,
1≤ai≤2×10^9
输入样例：
3
2
6
8
输出样例：
12

参考： 《算法竞赛进阶指南》。

约数个数计算公式（算术基本定理推论）：

根据唯一分解定理，每个约数由它的因式分解式唯一确定，

所以约数个数就是：$b_1,b_2,…,b_m$每个指数选择的个数（有范围限定）的组合的个数。（乘法原理）

代码：

#include <iostream>
#include <algorithm>
#include <unordered_map>
typedef long long LL;
using namespace std;
const int MOD = 1e9 + 7;
int n;

int main(){
    cin >> n;
    int x;
    // primes下标会很大，用vector不合适，需要哈希表
    unordered_map<int,int> primes;
    while (n -- ){
        cin >> x;
        for (int i = 2;i <= x / i;i ++){
            while (x % i == 0){
                primes[i]++;
                x /= i;
            }
        }
        if (x != 1) primes[x]++;
    }
    LL res = 1; // 从1开始乘，不是0
    for (auto it : primes)
        res = res * (it.second + 1) % MOD;
    cout << res << '\n';
    return 0;
}

---

怎么计算一个数n大约有多少个约数？

我们先计算1~n中总共的约数的个数。a是b的约数，那么b是a的倍数，以a为约数的数就是a的倍数。由此可以计算n的约数个数大概是n / d，1~n中总共的约数的个数大概是：

$n + n/2 + n/3 + … + n/n \approx n \star ln n < n \star log_2 n$。

所以平均来看一个数n的约数个数大概是$log n$。

例题：871. 约数之和（模板题）

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

输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。

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

数据范围
1≤n≤100,
1≤ai≤2×10^9
输入样例：
3
2
6
8
输出样例：
252

#include <iostream>
#include <algorithm>
#include <unordered_map>
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
int n;

int main(){
    cin >> n;
    int x;
    unordered_map<int,int> hash;
    while (n -- ){
        cin >> x;
        for (int i = 2; i <= x/i; i ++ ){
            while (x % i == 0){
                x /= i,hash[i]++;
            }
        }
        if (x > 1) hash[x]++;
    }
    
    LL res = 1;
    for (auto prime : hash){
        LL t = 1,a = prime.first,b = prime.second;
        while (b--) t = (t*a + 1) % MOD;
        res = (res * t) % MOD;
    }
    cout << res << '\n';
    return 0;
}