约数之和定理
定理内容
对于一个大于1正整数n可以分解质因数 $ n=\prod_{i=1}^kp_i^{a_i}=p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k} $
则n的所有正约数的和就是
$$
f(n) = \prod_{i=1}^k(p_i^0 + p_i^1 + \cdots + p_i^{a_i})
= (p_1^0 + p_1^1 + \cdots + p_1^{a_1}) \cdot (p_2^0 + p_2^1 + \cdots + p_2^{a_2}) \cdots (p_k^0 + p_k^1 + \cdots + p_k^{a_k})
$$
简要证明
若n可以分解质因数:$ n=\prod_{i=1}^kp_i^{a_i}=p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k} $,
可知 $p_1^{a_1}$ 的约数有$p_1^0, p_1^1, p_1^2 \cdots p_1^{a_1}$
……
同理可知, $p_k^{a_k}$ 的约数有$p_k^0, p_k^1, p_k^2 \cdots p_k^{a_k}$
实际上n的约数是在$p_1^{a_1}, p_2^{a_2} \cdots p_k^{a_k}$ 中的每一个约数中分别挑一个相乘得来的
可知共有$(a_1+1)(a_1+1) \cdots (a_k+1)$ 种挑法,即约数的个数
由乘法原理可知他们的和为:
$$
f(n) = \prod_{i=1}^k(p_i^0 + p_i^1 + \cdots + p_i^{a_i})
= (p_1^0 + p_1^1 + \cdots + p_1^{a_1}) \cdot (p_2^0 + p_2^1 + \cdots + p_2^{a_2}) \cdots (p_k^0 + p_k^1 + \cdots + p_k^{a_k})
$$
代码如下
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int MOD = 1e9 + 7;
/**
* acwing 871-约数之和
*/
int main() {
int n;
scanf("%d", &n);
unordered_map<int, int> primes;
while (n--) {
int x;
scanf("%d", &x);
for (int i = 2; i <= x / i; i++) {
while (x % i == 0) {
x /= i;
primes[i]++;
}
}
if (x > 1) primes[x]++;
}
LL res = 1;
for (auto prime : primes) {
int p = prime.first, a = prime.second;
LL t = 1;
while (a--) {
t = (t * p + 1) % MOD;
}
res = res * t % MOD;
}
cout << res << endl;
return 0;
}