AcWing 870. 约数个数

题目

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

输入格式 第一行包含整数 $n$。

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

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

数据范围 $1≤n≤100,1≤a_i≤2×10^9$ 输入样例：

3
2
6
8

输出样例：

12

思路

约数个数定理： 对于一个大于1正整数n可以分解质因数： $n = {p_1}^{a_1}{p_2}^{a_2}...*{p_k}^{a_k}$ 则 $n$ 的正约数的个数就是 $sum = (a_1 + 1) * (a_2 + 1) * ... * (a_k + 1)$。 其中 $a1、a2、a3…ak$ 是 $p1、p2、p3，…pk$ 的指数。

定理简证 首先同上，$n$ 可以分解质因数：$n = {p_1}^{a_1}{p_2}^{a_2}...*{p_k}^{a_k}$, 由约数定义可知 ${p_1}^{a_1}$ 约数有: $p_1^0, p_1^1, p_1^2, ...$，共（$a_1+1$）个；同理 ${p_2}^{a_2}$ 的约数有 $(a_2+1)$ 个；……；${p_k}^{a_k}$ 的约数有 $(a_k+1)$ 个。 故根据乘法原理：$n$ 的约数的个数就是 $(a_1+1)(a_2+1)(a_3+1)…(a_k+1)$。

本题中，我们通过试除法求出每个约数最大个数，即上述公式中的指数，将结果按公式计算即可。

代码

#include <iostream>
#include <unordered_map>

typedef long long LL;

using namespace std;

const int mod = 1e9 + 7;

int n;

int main()
{
    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;
}