59.Acwing基础课第870题-简单-约数个数
题目描述
给定\(n\)个正整数 \(a_i\)，请你输出这些数的乘积的约数个数，答案对 109+7 取模。
输入格式
第一行包含整数 \(n\)。
接下来 \(n\) 行，每行包含一个整数 \(a_i\)。
输出格式
输出一个整数，表示所给正整数的乘积的约数个数，答案需对109+7 取模。
输出格式
数据范围
1≤\(n\)≤100
1≤\(a_i\)≤2×109
输入样例：
3
2
6
8
输出样例：
12
代码：
// 包含标准输入输出头文件（cin/cout依赖）
#include <iostream>
// 算法库（本代码未直接使用，属于通用模板保留）
#include <algorithm>
// 哈希表头文件：用于高效统计质因子的总指数（key=质因子，value=总指数）
#include <unordered_map>
// 向量容器头文件（本代码未直接使用，属于通用模板保留）
#include <vector>// 使用std命名空间，避免重复写std::
using namespace std;// 定义长整型别名LL：防止计算过程中数值溢出（约数个数可能很大，超过int范围）
typedef long long LL;// 常量定义：
// N=110（本代码未使用，仅为模板保留）；mod=1e9+7（结果取模的模数，避免数值过大）
const int N = 110, mod = 1e9 + 7;int main()
{int n; // n：输入的正整数的个数（最终求这n个数乘积的约数个数）cin >> n; // 输入n// 哈希表primes：统计n个数乘积的所有质因子及其总指数// key：质因子（如2、3、5）；value：该质因子在乘积中的总指数（所有数分解后该质因子的指数和）unordered_map<int, int> primes;// 循环处理每个输入的正整数xwhile (n -- ){int x; // x：当前需要分解质因数的数cin >> x; // 输入x// 分解x的质因数：枚举2到√x的所有数（i <= x/i 等价于 i <= sqrt(x)，避免浮点精度误差）for (int i = 2; i <= x / i; i ++ )// 若i是x的质因子，循环除净并统计指数while (x % i == 0){x /= i; // 把x中的质因子i除干净primes[i] ++ ; // 该质因子的总指数+1（累加到哈希表）}// 若循环结束后x>1，说明剩下的x是一个大于√原数的质因子，总指数+1if (x > 1) primes[x] ++ ;}// 约数个数定理：若一个数N的质因数分解为 N = p1^a1 * p2^a2 * ... * pn^an// 则N的约数个数 = (a1+1) * (a2+1) * ... * (an+1)（每个质因子的指数+1后相乘）LL res = 1; // 初始化结果为1（乘法的单位元）// 遍历哈希表中所有质因子及其总指数，计算约数总数for (auto p : primes) // 核心计算：(当前结果) * (该质因子指数+1)，结果对mod取模（防止数值溢出）res = res * (p.second + 1) % mod;cout << res << endl; // 输出最终的约数个数（取模后）return 0; // 程序正常结束
}