题目描述

blablabla

算法1

blablabla

时间复杂度

参考文献

https://www.acwing.com/solution/content/4969/

C++ 代码

#include<iostream>
#include<algorithm>
#include<unordered_map>

using namespace std;
typedef long long   LL;

const int mod = 1e9+7;

int n, m;

int main () {

    scanf("%d", &n);
    LL ans = 1;
    unordered_map<int, int> prime;// 哈希表存每个因数pi的指数（pi的个数） 

    while (n--) {
        int x;
        scanf("%d", &x);
        for (int i = 2; i <= x / i; i++) {//试除法求因数i的指数 
            while (x % i == 0) {
                x /= i;
                prime[i] ++;//
            }
        }
        if ( x > 1) prime[x] ++;//如果最后除剩下的因数不是1，则也要存入 
    }
    for (auto i : prime)    ans = ans * (i.second + 1) % mod;
    //每次都取模，避免数据过大溢出 
    cout << ans <<endl;
    return 0;
} 

求约数总个数：
假设n的约数分别是p1~pk，并且他们对应指数a1~ak
那么用组合法n的约数可以是P1*p2,,等等，任意组合
可以选0个p1，1个p1，两个p1，,a1个p1，，

那么按照排列组合就可以得出约数个数即