4397: 【入门】乘积的约数个数(2138)
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：2
题目描述
给定 个正整数 ，请你输出这些数的乘积的约数个数，答案对 取余数。
输入
第一行包含整数 。
接下来 行，每行包含一个整数 。
数据范围：
输出
输出一个整数，表示所给正整数的乘积的约数个数。
样例输入 复制
5
3
2
4
18
11样例输出 复制
40提示
#include<bits/stdc++.h>
using namespace std;
/*
因数个数=(a1+1)*(a2+1)*(a3+1)*......*(ai+1)
1. 所有的数相乘，分解质因子，得到质因子及个数
和每个数单独分解质因子，得到质因子及个数，答案一致
2. 每个数相加的结果%10000，和两个数%10000相加，再%10000，结果一致
3. 乘法同理
本题的思路：
将每个数分解质因子，求出每个质因子出现的次数，按公式求解约数个数
*/
int n,x;
map<int,int> m;
map<int,int>::iterator it;
typedef long long LL;
const int M=1e9+7;
LL r=1;
int main(){
cin>>n;
for(int i=1;i<=n;i++) {
cin>>x;
//分解x的质因子
for(int j=2;j<=sqrt(x);j++){
while(x%j==0){
m[j]++;
x=x/j;
}
}
if(x>1) m[x]++;
}
for(it=m.begin();it!=m.end();it++) {
r=r*(it->second+1)%M;
}
cout<<r;
return 0;
}