算术基本定理

一个数可以分解成若干个质数的乘积。

$x = p_1^{a_1} + p_2^{a_2} + … + p_k^{a_k}$

约数个数

思路

根据组合数学，设cnt为约数个数；

cnt = (a1 + 1) * (a2 + 1) * ... * (an + 1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n,d;

int cnt(int x) {
    int res = 1;
    for(int i = 2; i * i <= x; ++ i) {
        if(x % i == 0) {
            int s = 0;
            while(x % i == 0) x /= i, ++ s;
            res *= (s + 1);
        }
    }
    if(x > 1) res *= 2;
    return res;
}

约数和

思路

设res为约数和，不难看出：

$res = (p_1^0 + … + p_1^{a_1}) \times … \times (p_k^0 + … + p_k^{a_k})$

约数之和

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

输入格式

第一行包含整数 $n$。

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

输出格式

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

数据范围

$1\leq n\leq 100,1\leq a_i\leq 2 \times 10^9$

输入样例：

1
2
3
4
3
2
6
8

输出样例：

1
252

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int M = 1e9 + 7;

int n;
int val;

unordered_map<int,int> primes;

void get(int x) {
    for(int i = 2; i * i <= x; ++ i) {
        if(x % i == 0) {
            int s = 0;
            while(x % i == 0) x /= i, ++ s;
            primes[i] += s;
        }
    }
    if(x > 1) primes[x] += 1;
}

LL get_val(int x) {
    LL res = 1;
    for(int i  = 1; i <= primes[x]; ++ i)
        res = res * x % M + 1 % M;
    return res;
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; ++ i) {
        cin >> val;
        get(val);
    }
    LL res = 1;
    for(auto p : primes)
       res = (LL)res * get_val(p.first) % M;
    cout << res << endl;
    return 0;
}