AcWing 870. 约数个数
原题链接
简单
作者:
渐修
,
2024-04-10 18:08:16
,
所有人可见
,
阅读 2
/*
假设n的质因子为p1,p2,p3...pn,指数为a1,a2,a3...an,由组合数可知,约数个数为
(a1+1)(a2+1)(a3+1)...(an+1)
*/
#include<iostream>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int n,x;
unordered_map<int,int> primes;//存键值对(素数,指数)
void dive(int n)//分解质因子
{
for(int i=2;i<=n/i;i++)
{
if(n%i==0)
{
while(n%i==0)
{
primes[i]++;
n/=i;
}
}
}
if(n>1)
primes[n]++;
}
int main()
{
cin>>n;
while(n--)
{
cin>>x;
dive(x);
}
ll ans=1;
for(auto t:primes)
ans=ans*(t.second+1)%mod;
cout<<ans;
return 0;
}