题目描述
给定 n 个正整数 ai,请你输出这些数的乘积的约数个数,答案对 109+7 取模。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个整数 ai。
输出格式
输出一个整数,表示所给正整数的乘积的约数个数,答案需对 109+7 取模。
数据范围
1≤n≤100,
1≤ai≤2×109
样例
输入样例:
3
2
6
8
输出样例:
12
算法1
本题要求输出一个数的因数的个数
核心原理
本题给出n个数,要求给出n个数乘积的因数个数。
我们使用一个哈希表,将n个数都分解为质因数,并将次数也记录下来,分解完毕之后就得到了乘积的质因数和次数。
按照公式即可得出答案。
C++ 代码
#include <iostream>
#include <unordered_map>
using namespace std;
const int mod = 1e9+7;
int main(){
int n;
cin>>n;
unordered_map<int,int> primes;
while(n--){
int x;
cin>>x;
for(int i = 2;i<=x/i;i++){
while(x%i==0){
x/=i;
primes[i]++;
}
}
if(x!=1)primes[x]++;
}
long long result = 1;
for(auto prime:primes){
result = result*(prime.second+1)%mod;
}
cout<<result<<endl;
return 0;
}
牛哇牛蛙, 还是举例更具体
好饱满