算法思想
任意一个数都可以展开为各个质因数的乘积
n = p1^a1 * p2^a2 * … * pk^ak (其中p1, p2, …, pk为n得质因数)
约数的表现形式: p1^x1 * p2^x2 * … * pk^xk
其中x1取值范围: 0 ~ a1, x2取值范围: 0 ~ a2, … , xk取值范围: 0 ~ ak
第k项取值个数为ak + 1
将每一项的可能取值的个数连乘,得
约数个数 = (a1 + 1)(a2 + 1) … (ak + 1)
第k项可能取值为: pk^0, pk^1, … ,pk^ak
将每一项可能取值连乘,得
约数之和 = (p1^0 + p1^1 + p2^2 +…+ p1^a1)(p2^0 + p2^1 + p2^2 +…+ p2^a2)…(pk^0 + pk^1 + pk^2 +…+ pk^ak)
#include <iostream>
#include <unordered_map>
using namespace std;
const int mod = 1e9 + 7;
unordered_map<int, int> primes;
int main()
{
int n;
cin >> n;
while (n --) //将每个数的质因数个数用哈希表存储
{
int x;
cin >> x;
for (int i = 2; i <= x / i; i ++)
{
while (x % i == 0) //每次将质因数i除干净
{
primes[i] ++;
x /= i; //每次需要除掉已经统计的质因子
}
}
if (x > 1) primes[x] ++; //x含大于√x的质因数
}
long long res = 1;
for (auto u : primes)
{
long long val = u.first, num = u.second;
long long p = 1;
while (num --) p = (p * val + 1) % mod; //该项可能取值之和:val^0 + val^1 +...+ val^num
res = res * p % mod; //将每一项的可能取值连乘
}
cout << res << endl;
}