$\Huge\color{orchid}{点击此处获取更多干货}$

算术基本定理

接上帖，假设某正整数$N$按照$ {\textstyle \prod_{i=1}^{k}} (p_i^{a_i}) $来分解，那么由此，可以得出第二个推论，即所有约数的总和$P(N)= {\textstyle \prod_{i=1}^{k}} ({\textstyle \sum_{j=0}^{a_i}} (p_i^j))$，详细展开式如下：
$$P(N)=(1+p_1+p_1^2+…+p_1^{a_1})*(1+p_2+p_2^2+…+p_2^{a_2})*…*(1+p_k+p_k^2+…+p_k^{a_k})$$

用一下上帖中的图，再次说明正整数$N$的约数是怎么来的：

那么由此，可以用归纳法给出如下证明：

括号里的每一项都是等比数列，邻项公比为$p_i,i=1,2,…,k$，这个可以直接用公式$(p_i^{a_i+1}-1)/(p_i-1)$借助快速幂求解，也可以利用最大指数$k$和$k-1$时数列的和$S(k)=p*S(k-1)+1$来求，这里采用第二种方式，快速幂会在之后介绍

C++ 代码

主函数：

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, x;
    cin >> n;
    //对构成乘积的每一项分解质因数
    while (n--) {
        cin >> x;
        primeFactorization(x);
    }
    size_t ans = 0;
    //对每一个质因数幂项按公式求和
    for (auto& [p, a] : primes) {
        ans = (ans * sumOfSeries(p, a)) % MOD;
    }
    cout << ans << endl;
    return 0;
}

跟上次一样，需要把构成乘积的每个数分解质因数

/**
 * @brief 分解质因数
 * @param x 待分解的数
 * 将质因数的分解结果存入哈希表primes
 */
void primeFactorization(int x) {
    for (int i = 2; i <= x / i; i++) {
        while (x % i == 0) {
            primes[i]++;
            x /= i;
        }
        if (x > 1) {
            primes[x]++;
        }
    }
}

每个质因数对应的等比数列和，求解方法如下：

/**
 * @brief 求1+p+p^2+...+p^a
 * @param base 底数（相当于p）
 * @param pow 最高指数（相当于a）
 * @return 底数为p，指数为0~a的幂项累加和
 * 累加的递推关系：S(a + 1) = p * S(a) + 1
 */
size_t sumOfSeries(int base, int pow) {
    size_t sum = 0;
    for (int i = 0; i <= pow; i++) {
        sum = (sum * base + 1) % MOD;
    }
    return sum;
}

为了避免溢出，上述所有结果全都采用size_t类型