【算法】约数之和（数论）

题目

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

输入格式

第一行包含整数 n。

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

输出格式

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

数据范围

1≤n≤100
1≤ai≤2×1e9

输入样例：

3
2
6
8

输出样例：

252

思路

首先，使用unordered_map primes 来记录每个质因子及其出现的次数。

然后，对于每个输入的数x，通过质因数分解的方法，将x进行质因数分解，并统计每个质因子的次数。如果x仍然大于1，说明x本身就是一个质因子，将其次数加1。

接下来，遍历primes中的每个质因子及其次数。对于每个质因子a，计算它的幂和(a^b + 1) % mod，其中b为该质因子的次数。最后，将每个质因子的幂和乘到约数和中，得到最终的约数和。

最后，输出约数和的结果。

其中用到公式：

其中：p1~pk代表质因数，c1~ck代表质因数个数

结束后t为

t = a^b + a^(b-1) + a^(b - 2) + .... + a^3 + a^2 + a^1 + a^0

代码

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>using namespace std;typedef long long LL;const int N = 110, mod = 1e9 + 7;int main()
{int n;cin >> n; // 输入n，表示有n个数unordered_map<int, int> primes; // 使用unordered_map来记录质因子及其次数while (n -- ){int x;cin >> x; // 输入每个数xfor (int i = 2; i <= x / i; i ++ )while (x % i == 0) // 对x进行质因数分解，并统计每个质因子的次数{x /= i;primes[i] ++ ;}if (x > 1) primes[x] ++ ; // 如果x仍然大于1，说明x本身就是一个质因子，将其次数加1}LL res = 1; // 初始化约数和为1for (auto p : primes) // 遍历primes中的每个质因子及其次数{LL a = p.first, b = p.second; // 质因子a和其次数bLL t = 1; // 计算质因子a的幂和while (b -- ) t = (t * a + 1) % mod;res = res * t % mod; // 将质因子a的幂和乘到约数和中}cout << res << endl; // 输出约数和return 0;
}

题目来自：871. 约数之和 - AcWing题库