871 约数之和

如果 N = p1^c1 * p2^c2 * … *pk^ck
约数之和： (p1^0 + p1^1 + … + p1^c1) * … * (pk^0 + pk^1 + … + pk^ck)

如下代码块便是来求约数之和

ll ans = 1;
for (auto prime : primes){
    int pi = prime.first, ci = prime.second;
    ll t = 1;    // t 用来求(pi^0 + pi^1 + ... + pi^ci)，初始化为1
    while (ci --){
        t = (t * pi + 1) % mod; // t 每次乘以pi，再加上1，其实就是(pi^0 + pi^1 + ... + pi^cn)，
        // 执行ci次最后就是(pi^0 + pi^1 + ... + pi^ci)
    }
    ans = (ans * t) % mod;
}

AC代码：

#include <iostream>
#include <unordered_map>
using namespace std;

typedef long long ll;
const int mod = 1e9 + 7;
int n, a;
ll res = 1;
unordered_map<int, int> primes;

int main(){
    cin >> n;
    while (n --){
        cin >> a;
        for (int i = 2; i <= a / i; i ++){
            while (a % i == 0){
                a /= i;
                primes[i] ++;
            }
        }
        if (a > 1) primes[a] ++;
    }

    ll ans = 1;
    for (auto prime : primes){
        int p = prime.first, q = prime.second;
        ll t = 1;  // 不能初始化为0!
        while (q --){
            t = (t * p + 1) % mod;
        }
        ans = (ans * t) % mod;
    }

    cout << ans << endl;

    return 0;

}