给定n个正整数ai,请你输出这些数的乘积的约数之和,答案对109+7取模。
输入格式
第一行包含整数n。
接下来n行,每行包含一个整数ai。
输出格式
输出一个整数,表示所给正整数的乘积的约数之和,答案需对109+7取模。
数据范围
1≤n≤100,
1≤ai≤2∗109
输入样例:
3
2
6
8
输出样例:
252
每个因子pk可以选0-ak个
因此约数个数ans=(a1+1)*(a2+1)*(a3+1)*.....*(ak+1)
展开即为所有约数的和
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int main()
{
ll k;
cin>>k;
unordered_map<ll,ll> primes;
//给每个数分解质因数的过程
//x 的质因子最多只包含一个大于 根号x 的质数。
//如果有两个,这两个因子的乘积就会大于 x,矛盾
while (k--)
{
ll x;
cin>>x;
for(ll i=2;i<=x/i;i++)
while(x%i==0)
{
x/=i;
primes[i]++; //i为因子,primes[i]为底数;
}
if(x>1)primes[x]++; //剩余的大于sqrt(x)的因子;
}
ll res=1;
for (auto p:primes)
{
ll a=p.first,b=p.second;
ll t=1;
while (b--)t=(t*a+1)%mod; //可得到pk的0次方到k次方的和;
res=res*t%mod;
}
cout<<res<<endl;
}