题目描述
给定 n 个正整数 ai,请你输出这些数的乘积的约数之和,答案对 109+7 取模。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个整数 ai。
输出格式
输出一个整数,表示所给正整数的乘积的约数之和,答案需对 109+7 取模。
数据范围
1≤n≤100,
1≤ai≤2×109
样例
输入样例:
3
2
6
8
输出样例:
252
算法1
N=P1^a1+P2^a1+....Pk^ak
和等于(p1^0+p1^1…+p1^a1)+…+(pk^1+pk^1+..+pk^k)
和约数个数类似,只需要首先求出p1^0+p1^1…即可,这里使用t=(t*p+1)求解即可
C++ 代码
/*
N=P1^a1+P2^a1+....Pk^ak
和等于(p1^0+p1^1...+p1^a1)+...+(pk^1+pk^1+..+pk^k)
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
int main()
{
int n;
cin>>n;
//哈希表存储所有底数和指数
unordered_map<int,int>primes;
while(n--)
{
int x;
cin>>x;
//从2开始枚举
for(int i=2;i<=x/i;i++)
while(x%i==0)
{
x/=i;
primes[i]++;//存了所有的质因数的质数加1
}
if(x>1) primes[x]++;//当x足够大时
}
long long res=1;
for(auto prime:primes)
{
int p=prime.first;
int a=prime.second;
long long t=1;
while(a--) t=(t*p+1)%mod;
res=res*t%mod;
}
cout<<res<<endl;
return 0;
}