约数个数

给定 $n$ 个正整数 $a_i$，求出这些数的乘积的约数个数。
我们朴素的做法是，先将这 $n$ 个数乘起来，再用getDivisors()求出所有约数来获得约数个数，但这种方法在这 $n$ 个数的乘积很大的时候就做不了（会溢出）。

比较优的方法是：分别用getPrimes()求出这 $n$ 个数的质因数的个数和次数，这时候：
$$ a_i = \prod p_j ^ {c_j} $$
从这可以获得 $a_i$的质因数和次数，这样获得其他数的质因数和次数之后，我们可以用组合的知识来获得每个因数的个数，所以这 $n$ 个数的乘积最终可以化为：
$$ \prod a_i = \prod p_j ^ {c_j} $$
对于每个 $p_j$ 都有 $c_j$ 个，可以枚举：$1, p_j,p_j ^ 2…p_j^{c_j}$，共 $c_j + 1$ 种因子。

最后用组合数学来求出因子的个数：
$$ ans = \prod (c_j + 1) $$
代码

int getDivisorsNum(vector<int> muls){

    long long ans = 1;
    unordered_map<int, int> primes;

    for (auto it : muls){
        auto a = getPrimes(it);
        for (auto it2 : a)
            primes[it2.first] += it2.second;
    }

    for (auto it : primes)  ans = ans * (it.second + 1) % Mod;

    return ans;
}

完整代码

#include <bits/stdc++.h>

using namespace std;

const int Mod = 1e9 + 7;

typedef pair<int, int> pii;

vector<pii> getPrimes(int n){

    vector<pii> res;

    for (int i = 2; i <= n / i; i ++ ){
        int a = 0;
        while (n % i == 0)
            n /= i, a ++ ;
        if (a)  res.push_back({i, a});
    }
    if (n > 1)  res.push_back({n, 1});

    return res;
}

int getDivisorsNum(vector<int> muls){

    long long ans = 1;
    unordered_map<int, int> primes;

    for (auto it : muls){
        auto a = getPrimes(it);
        for (auto it2 : a)
            primes[it2.first] += it2.second;
    }

    for (auto it : primes)  ans = ans * (it.second + 1) % Mod;

    return ans;
}

int main(){

    vector<int> a;

    int n;
    cin >> n;
    while (n -- ){
        int x;
        cin >> x;
        a.push_back(x);
    }

    cout << getDivisorsNum(a);
    return 0;
}