题目描述

给定n个正整数ai,请你输出这些数的乘积的约数个数，答案对1e9取模

输入样例:

3
2
6
8

输出样例:

12

算法

(质因数分解+公式)

C++ 代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
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;
        for(int i=2;i<=x/i;i++){
            while(x%i==0){
                x/=i;
                primes[i]++;//用哈希表存因式分解中的指数
            }
        }
        if(x>1) primes[x]++;//如果还没分解清,说明剩下的这个数是它的因数且只有一个
    }
    LL res=1;
    for(auto prime:primes) res=res*(prime.second+1)%mod;//约数个数=(a1+1)(a2+1)...(ak+1)
    cout<<res<<endl;
    return 0;
}