【数学】约数个数

题目

870. 约数个数

---

给定 $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

输出样例：

12

解题

方法一：数学

思路

由算术基本定理，对一个正整数 $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} f(n) &= (\alpha_1 + 1)(\alpha_2 + 1) \cdots (\alpha_k + 1) \\ &= \prod_{i=1}^{k}{(\alpha_i + 1)} \end{aligned}$$

证明：
$n$ 的任何一个约数 $d$ 可以质因数分解表示为：$d = p_1^{\beta_1} \times p_2^{\beta_1} \times \cdots \times p_k^{\beta_k}, \,\,\,\,\, 0 \le \beta_i \le \alpha_i$ 。
每一项的 $\beta_i$ 如果不同，那约数 $d$ 就一定不同（由算术基本定理可知每个数的质因数分解是唯一的）。
所以 $n$ 的约数与其约数每一项选择 $\beta_1 \sim \beta_k$ 的选法是对应的，故 $n$ 的约数个数与选法的个数时相同的。对于 $n$ 的约数来说：$\beta_1$ 一共有 $0 \sim \alpha_1$ 共 $\alpha_1 + 1$ 种选法、$\beta_2$ 一共有 $0 \sim \alpha_2$ 共 $\alpha_2 + 1$ 种选法 …… $\beta_k$ 一共有 $0 \sim \alpha_k$ 共 $\alpha_k + 1$ 种选法。根据乘法原理，一共就有 $(\alpha_1 + 1)(\alpha_2 + 1) \cdots (\alpha_k + 1)$ 种选法。

本题求的是 $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 cnt = 1;
        for (int v : mp.values()) {
            cnt = cnt * (v + 1) % MOD;
        }
        System.out.println(cnt);
    }
}

#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 cnt = 1L;
    for (auto& pr : mp) cnt = (cnt * (pr.second + 1)) % MOD;
    printf("%d\n", cnt);
    
    return 0;
}