题目:给定n个数,求这n个数的乘积的约数个数
在解这道题之前,先引入一个公式(求一个正整数n的约数个数的公式)
$$\color{red}{若n可写成f(n)=a_1^{\alpha_1} \ast a_2^{\alpha_2} \ast \ldots\ast a_k^{\alpha_k}=\prod_{i=1}^k{(a_i^{\alpha_i})} \quad \color{brown}{(a_1,a_2, \ldots ,a_k 均为质数)}}$$
则n的约数的个数(quantity): $$\color{red}{quantity(n)=(\alpha_1+1) \ast (\alpha_2+1) \ast \ldots \ast (\alpha_k+1)=\prod_{i=1}^k{(\alpha_i+1)}}$$
证明:
$$\color{blue}{已知n可写成f(n)=a_1^{\alpha_1} \ast a_2^{\alpha_2} \ast \ldots\ast a_k^{\alpha_k}=\prod_{i=1}^k{(a_i^{\alpha_i})}}$$
①算出$a_1^{\alpha_1}$的约数个数 显然=$\alpha_1+1$个
①算出$a_2^{\alpha_2}$的约数个数 显然=$\alpha_2+1$个
$\ldots$
end:算出$a_k^{\alpha_k}$的约数个数 显然=$\alpha_k+1$个最后根据乘法原理可得:
n的约数的个数(quantity): $$\color{red}{quantity(n)=(\alpha_1+1) \ast (\alpha_2+1) \ast \ldots \ast (\alpha_k+1)=\prod_{i=1}^k{(\alpha_i+1)}}$$代码(C++)
#include<iostream>
#include<unordered_map>
using namespace std;
const long long mod=1e9+7;
int main()
{
int n;
long long res=1;
unordered_map<int,int> f;//f.first 存放底数,f.second存放f.first的指数
cin>>n;
while(n--)
{
int x;
cin>>x;
for(int i=2;i<=x/i;i++)
{
while(x%i==0)
{
f[i]++;
x/=i;
}
}
if(x>1) f[x]++;
}
for(auto t:f)
{
res=res*(t.second+1)%mod;
}
cout<<res;
return 0;
}