题目描述
给定n个正整数ai，请你输出这些数的乘积的约数个数，答案对109+7取模。
输入格式
第一行包含整数n。
接下来n行，每行包含一个整数ai。
输出格式
输出一个整数，表示所给正整数的乘积的约数个数，答案需对109+7取模。
数据范围
$ 1≤n≤100,$
(1≤ai≤2∗10^9)
输入样例：
3
2
6
8
输出样例：
12
解题思路
根据算数的进本定理可知任何一个大于1的自然数N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积 (N=P_1^{a_1} imes P_2^{a_2} imes P_3^{a_3} imes P_4^{a_4} imes... imes P_n^{a_n}(P_1,P_2,P_3...P_n均为质数)) 那么该数 N 的约数个数为: ((a1 + 1) imes (a_2 + 1) imes (a_3 + 1) imes (a_4 + 1) imes ... imes (a_n+1)) 所以我们直接根据公式一步步向下求即可。
- 看了许多dalao们写的题解全部都是用了一个叫“unordered_map”的容器。emmm......有关unordered_map的讲解请移步至（STL之unordered_map）暂时未写
代码样例
#include<iostream>
#include<unordered_map>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
unordered_map<int,int> hash;
int main(){
int t;
cin >> t;
while(t--){ // 质因数分解
ll n;
cin >> n;
for (int i = 2; i*i <= x; ++i){
while(n % i == 0){
hash[i] ++;
n /= i;
}
}
if (n > 1)
hash[n] ++; // 这一步不要忘记了
}
ll ans = 1;
for (auto n:hash){ // 约数的个数 (N1 + 1)*(N2 + 1)*(N3 + 1)*...
ans = ans*(n.second + 1) % MOD; // 别忘了取模
}
cout << ans << endl;
return 0;
}
完～