AcWing 871. 约数之和

题目

思路

1. 由约数之和定理可知约数之和公式为：$s(n) = ({p_1}^0 + {p_1}^1 + ... + {p_1}^{a_1})({p_2}^0 + {p_2}^1 + ... + {p_2}^{a_2})...({p_k}^0 + {p_k}^1 + ... + {p_k}^{a_k})$
2. 计算 $({p_1}^0 + {p_1}^1 + ... + {p_1}^{a_1})$ 可用秦九韶算法

LL t = 1;
while (x -- ) t = (t * p + 1) % mod;

代码

#include <iostream>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int mod = 1e9 + 7;

int n;

int main()
{
    cin >> n;
    unordered_map<int, int> primes;
    
    while (n -- )
    {
        int x;
        cin >> 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)
    {
        LL p = prime.first, x = prime.second;
        
        LL t = 1;
        while (x -- ) t = (t * p + 1) % mod;
        
        res = res * t % mod;
    }
    
    cout << res << endl;
    
    return 0;
}