算法：约数，约数个数，约数和，最大公约数(b ? gcd(b, a%b) : a；)

约数

计算约数时，只需计算到 n \sqrt{n} n ​就可以，大于 n \sqrt{n} n ​的约数可以通过用n除以小于 n \sqrt{n} n ​的约数得到。并且需要特判一下边界n / i != i。

void get_divosors(int n){
    vector<int> ans;
    for(int i = 1; i <= n / i; ++i){
        if (n % i == 0) {
            ans.push_back(i);
            if(n / i != i){
                ans.push_back(n / i);
            }
        }
    }
    sort(ans.begin(), ans.end());
    for(int i = 0; i < ans.size(); ++i){
        cout << ans[i] << " ";
    }
    cout << endl;
    return;
}

约数个数

约数个数定理

则n的正约数的个数就是

其中a1、a2、a3…ak是p1、p2、p3，…pk的指数。

首先同上，n可以分解质因数： n = p 1 a 1 × p 2 a 2 × p 3 a 3 ∗ … ∗ p k a k n=p_1^{a_1}×p_2^{a_2}×p_3^{a_3}*…*p_k^{a_k} n=p1a1​​×p2a2​​×p3a3​​∗…∗pkak​​，
由约数定义可知 p 1 a 1 p_1^{a_1} p1a1​​的约数有: p 1 0 , p 1 1 , p 1 2 . . . . . . p 1 a 1 p_1^0, p_1^1, p_1^2......p_1^{a1} p10​,p11​,p12​......p1a1​ ，共 ( a 1 + 1 ) (a_1+1) (a1​+1)个;同理 p 2 a 2 p_2^{a_2} p2a2​​的约数有 ( a 2 + 1 ) (a_2+1) (a2​+1)个… p k a k p_k^{a_k} pkak​​的约数有 ( a k + 1 ) (a_k+1) (ak​+1)个。
故根据乘法原理：n的约数的个数就是 ( a 1 + 1 ) ( a 2 + 1 ) ( a 3 + 1 ) … ( a k + 1 ) (a_1+1)(a_2+1)(a_3+1)…(a_k+1) (a1​+1)(a2​+1)(a3​+1)…(ak​+1)。
用unordered_map存储每一个质因数的指数。
问题描述

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

#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long LL;

const int N = 110, 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 p : primes) res = res * (p.second + 1) % mod;
    cout << res << endl;
    return 0;
}

约数之和

约数之和
其中p为质因子，a为质因子的指数
f ( n ) = ( p 1 0 + p 1 1 + p 1 2 + … p 1 a 1 ) ( p 2 0 + p 2 1 + p 2 2 + … p 2 a 2 ) … ( p k 0 + p k 1 + p k 2 + … p k a k ) f(n)=(p_1^0+p_1^1+p_1^2+…p_1^{a1})(p_2^0+p_2^1+p_2^2+…p_2^{a2})…(p_k^0+p_k^1+p_k^2+…p_k^{ak}) f(n)=(p10​+p11​+p12​+…p1a1​)(p20​+p21​+p22​+…p2a2​)…(pk0​+pk1​+pk2​+…pkak​)

#include<iostream>
#include<unordered_map>
using namespace std;
const int N = 100;
typedef long long LL;
LL mod = 1e9 + 7;

int main(){
    int n;
    cin >> n;
    unordered_map<int, LL> primes;
    while(n--){
        LL a;
        cin >> a;
        for(int i = 2; i <= a / i; ++i)
            while(a % i == 0){
                a /= i;
                primes[i] ++;
            }
            if(a > 1) primes[a] ++;
    }
    LL ans = 1;
    for (auto p : primes){
        LL cnt = 0;
        LL c = 1;
            LL a = p.first, b = p.second;
            LL t= 1;
            while(b --) t = (t * a + 1) % mod;
            ans = ans * t % mod;
    }
    cout << ans << endl;
    return 0;
}

最大公约数

int gcd(int a, int b){
	return b ? gcd(b, a%b) : a;
}