4398: 【入门】乘积的约数和(2139)
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
给定 个正整数 ，请你输出这些数的乘积的约数和，答案对 取余数。
输入
第一行包含整数 。
接下来 行，每行包含一个整数 。
数据范围
。
输出
输出一个整数，表示所给正整数的乘积的约数和。
样例输入 复制
5
3
2
4
18
11样例输出 复制
14880提示
#include<bits/stdc++.h>
using namespace std;
/*
因数之和=(p1^0+p1^1+...p1^a1)*(pi^0+pi^1+...pi^ai)
本题的思路：
将每个数分解质因子，求出每个质因子出现的次数，按公式求解约数个数
*/
int n,x;
map<int,int> m;
map<int,int>::iterator it;
typedef long long LL;
const int M=1e9+7;
LL r=1,t,s;
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++) {
//求 (pi^0+pi^1+...pi^ai)
s=0;
t=1; //t表示pi^ai
for(int i=0;i<=it->second;i++) {
s=(s+t)%M;
t=(t*it->first)%M;
}
r=(r*s)%M;
}
cout<<r;
return 0;
}