【数学】约数之和

题目

871. 约数之和

---

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

输入格式

第一行包含整数 $n$ 。

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

输出格式

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

数据范围

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

输入样例：

3
2
6
8

输出样例：

252

解题

方法一：数学

思路

由算术基本定理，对一个正整数 $n$ 进行分解质因数：$n = \prod_{i=1}^{k}{p_i^{\alpha_i}} = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \cdots \times p_k^{\alpha_k}$ 。

那么 $n$ 的约数之和为：

$$\begin{aligned} \sigma(n) &= (p_1^0+p_1^1+p_1^2+ \cdots + p_1^{\alpha_1})(p_2^0+p_2^1+p_2^2+ \cdots + p_2^{\alpha_2}) \cdots (p_k^0+p_k^1+p_k1^2+ \cdots + p_k^{\alpha_k}) \\ &= \prod_{i=1}^{k}{(\sum_{j=0}^{\alpha_k}{p_i^j})} \end{aligned}$$

证明：
$n$ 的质因数 $p_1^{\alpha_1}$ 的约数为：$p_1^0, p_1^1, p_1^2, \cdots, p_1^{\alpha_1}$ ，那么同理， $p_k^{\alpha_k}$ 的约数为：$p_k^0, p_k^1, p_k^2, \cdots, p_k^{\alpha_k}$ 。
实际上 $n$ 的约数是在 $p_1^{\alpha_1}, p_12^{\alpha_2}, \cdots, p_k^{\alpha_k}$ 每一个点约数中分别挑一个相乘得来的，所以一共有约数个数种挑法，由乘法原理算出它们的和为：$(p_1^0+p_1^1+p_1^2+ \cdots + p_1^{\alpha_1})(p_2^0+p_2^1+p_2^2+ \cdots + p_2^{\alpha_2}) \cdots (p_k^0+p_k^1+p_k1^2+ \cdots + p_k^{\alpha_k})$ 。

本题求的是 $n$ 个数乘在一起的约数之和，具体做法是：把每个数都分别做质因数分解，统计并累和每个质因子的指数，然后根据上面给出的公式算出约数之和。

分解质因数的做法见：【数学】分解质因数。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int MOD = (int) 1e9 + 7;
    static Map<Integer, Integer> mp;
    
    static void pf(int n) {
        for (int i = 2; i <= n / i; ++i) {
            if (n % i == 0) {
                int s = 0;
                while (n % i == 0) {
                    n /= i;
                    ++s;
                }
                mp.put(i, mp.getOrDefault(i, 0) + s);
            }
        }
        if (n > 1) mp.put(n, mp.getOrDefault(n, 0) + 1);
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        mp = new HashMap<>();
        while (n-- > 0) {
            in.nextToken();
            pf((int) in.nval);
        }
        long sum = 1L;
        for (Map.Entry<Integer, Integer> entry : mp.entrySet()) {
            int p = entry.getKey(), a = entry.getValue();
            long tmp = 1L;
            while (a-- > 0) tmp = (tmp * p + 1) % MOD;
            sum = sum * tmp % MOD;
        }
        System.out.println(sum);
    }
}

#include <iostream>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int MOD = 1e9 + 7;
unordered_map<int, int> mp;

void pf(int n) {
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            int s = 0;
            while (n % i == 0) {
                n /= i;
                ++s;
            }
            mp[i] += s;
        }
    }
    if (n > 1) ++mp[n];
}

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        int a;
        scanf("%d", &a);
        pf(a);
    }
    LL sum = 1L;
    for (auto& pr : mp) {
        int p = pr.first, a = pr.second;
        LL tmp = 1L;
        while (a--) tmp = (tmp * p + 1) % MOD;
        sum = (sum * tmp) % MOD;
    }
    printf("%d\n", sum);
    
    return 0;
}