题目描述
给你 $n$ 个正整数 $a_1,a_2,a_3,…,a_n$,求 $a_1\times a_2\times a_3\times … \times a_n$ 的因数个数对 $10^9+7$ 取模的结果。
样例
输入样例1:
3
2
6
8
输出样例1:
12
算法
首先我们需要知道一个小学奥数知识:
如果一个正整数 $n$ 可被分解为 $p_1^{r_1}p_2^{r_2}p_3^{r_3}…p_k^{r_k}$(其中 $p_1,p_2,p_3,…,p_k$ 均为质数,$r_1,r_2,r_3,…,r_k$ 为大于等于 $1$ 的正整数),那么 $n$ 的因数个数为 $(r_1+1)(r_2+1)(r_3+1)…(r_k+1)$.
但是因为 $a_1\times a_2\times a_3\times … \times a_n$ 的结果可能过大,所以我们可以先统计出每一个 $a_i$ 的质因数个数,最后把它们加起来即可。
(详情见 867 分解质因数 题解)
#include <iostream>
#include <cstdio>
#include <unordered_map> //用哈希表存储质数
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
int main() {
int n;
scanf("%d", &n);
unordered_map<int, int> prime;
while (n --) {
int x;
scanf("%d", &x);
for (int i = 2; i <= x/i; ++i) { //分解质因数
while (x % i == 0)
prime[i] ++, x /= i;
}
if (x > 1)
prime[x] ++;
}
ll res = 1;
for (auto i : prime)
res = res * (i.second+1) % mod;
//运用公式计算,注意每次算完都要取模,否则可能溢出
printf("%lld", res);
return 0;
}