python/TangDou/AcWing/Divisor/871.md

##AcWing 871. 约数之和

一、题目描述

给定 n 个正整数 a_i，请你输出这些数的乘积的约数之和，答案对 10^9+7 取模。

输入格式 第一行包含整数 n。

接下来 n 行，每行包含一个整数 a_i。

输出格式 输出一个整数，表示所给正整数的乘积的约数之和，答案需对 10^9+7 取模。

数据范围 1≤n≤100,1≤a_i≤2×10^9

输入样例：

3
2
6
8

输出样例：

252

二、约数和定理

方法：

\LARGE 　(p_1^0+p_1^1+…+p_1^{r_1})\times (p_2^0+p_2^1+…+p_2^{r_2}) \times…\times(p_k^0+p_k^1+…+p_k^{r_k})

以360举例,求它的全部约数和:

\LARGE 360 =  2*2*2*3*3*5 =2^3 * 3^2 * 5^1

约数和就是：

\LARGE (2^0+2^1+2^2+2^3)*(3^0+3^1+3^2)*(5^0+5^1)  = \\
 \LARGE  (1+2+4+8)*(1+3+9)*(1+5)= \\ 
 \LARGE  15*13*6=1170$$

### 三、实现代码
```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;
#define int long long
typedef pair<int, int> PII;
const int N = 110;
const int MOD = 1e9 + 7;
unordered_map<int, int> primes;
int n;

signed main() {
    cin >> n;
    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]++;
    }

    int res = 1;
    for (auto p : primes) {
        int a = p.first, b = p.second; // 质数，几个
        int t = 1;
        while (b--) t = (t * a + 1) % MOD;
        res = res * t % MOD;
    }
    printf("%lld\n", res);
}
```

###　五、关键代码讲解
```cpp {.line-numbers}
 while (b--) t = (t * a + 1) % MOD;
```
这句话怎么理解？

<font color='red' size=6><b>结论： 每次都是上次运算结果$*a+1$</b></font>

原理：其实，对于每个质因子，是在计算:
$$\LARGE a^0+a^1+a^2+...+a^{k-1}+a^k= \sum_{i=0}^k a^i$$

这东西用代码怎么表示呢？
$$\LARGE \sum_{i=0}^k a^i= a^k+a^{k-1}+...+a^2+a^1+a^0 = \\
 \LARGE a^k+a^{k-1}+...+a^2+a^1+1 

按代码来逆向理解,核心思路：乘a+1： 第一步：\LARGE t=1,t=(a+1) 第二步：\LARGE t=t*a+1=a*(a+1)+1=a^2+a+1 第三步：\LARGE t=t*a+1=a*(a^2+a+1)+1 =a^3+a^2+a+1

符合上面的运算逻辑，是正确的计算办法。

举栗子：

\large 3^0+3^1+3^2+3^3+3^4+3^5