AcWing--870.约数个数

目录

题目：

分析：

代码：

题目：

给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 10^9+7 取模。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个整数 ai。

输出格式

输出一个整数，表示所给正整数的乘积的约数个数，答案需对 10^9+7取模。

数据范围

1≤n≤100,
1≤ai≤2×10^9

时/空限制

1s / 64MB

输入样例：

3
2
6
8

输出样例：

12

分析：

假设一个数 N=p1^a1·p2^a2···pk^ak(p为质数)......①

N 的任意一个约数 a=p1^b1·p2^b2···pk^bk（其中 0<=bi<=ai）......②

即 N 的任意一个约数都可以用②这种形式表示，而每一个bi的取值范围都在 0~ai 之间，并且N的任意两个约数之间，只要有一个 bi 不相同，那么这两个约数就不相同（算法基本定理）

因为 bi 的取值共有 0~ai 共 （ai+1） 个取值

所以

公式一：

N的约数个数= (a1+1)(a2+1)···(ak+1) 个

ps：int 范围内的数的约数个数最多为1500个左右。

拓展：同时还可以推出另外一个 公式

公式二：

N的约数之和=(p1^0+p1^2+···+p1^a1)·(p2^0+p2^1+···+p2^a2)···(pk^0+pk^1+···+pk^ak)

自己拆开来看看，就会发现其实就是每个约数的排列组合的和。

代码：

#include <iostream>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int N = 110, mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;

    // unordered_map 是 C++ 中的一个关联容器，它提供了一种高效的方式来维护一个由键和值组成的集合，其中每个键都是唯一的。这个容器使用哈希表来实现，因此它能够在常数时间内完成查找、插入和删除操作，这使得它比使用红黑树实现的 map 容器在某些情况下更加高效。
    unordered_map<int, int> primes; // 用于存这些数的乘积因式分解后的所有底数和指数

    // 分别分解每一个数的质因数，再累加，就可得到所有数乘积的质因数的个数
    while (n -- )
    {
        int x;
        cin >> x;

        // 第一步：分解质因数,即求x的每个质因数的个数。x=p1^a1·p2^a2···pk^ak（例如x=16，16=2*2*2*2=2^4，16由4个质因数2构成，则primes[2]=4，用哈希表存）
        for (int i = 2; i <= x / i; i ++ )
            while (x % i == 0)
            {
                x /= i;
                primes[i] ++ ;
            }

        if (x > 1) primes[x] ++ ; // x是质数的情况
    }

    // 第二步：求约数个数
    LL res = 1;
    for (auto p : primes) res = res * (p.second + 1) % mod;// 公式一：N的约数个数=(a1+1)(a2+1)···(ak+1)个

    cout << res << endl;

    return 0;
}