算法基础课

给定 nn 个正整数 aiai，请你输出这些数的乘积的约数之和，答案对 109+7109+7 取模。

输入格式

第一行包含整数 nn。

接下来 nn 行，每行包含一个整数 aiai。

输出格式

输出一个整数，表示所给正整数的乘积的约数之和，答案需对 109+7109+7 取模。

数据范围

1≤n≤1001≤n≤100,
1≤ai≤2×1091≤ai≤2×109

输入样例：

3
2
6
8

输出样例：

252

核心思路：这一题其实和约数的个数是有一定的关联的，本质也是一样的，先分解质因数:\(a=p_1^{k_1}*p_2^{k_2}\cdots p_n^{k_n}\),然后我们会发现把\(p_1^{k_1}\)的幂数给拆开，也就是\((1+p_1+p_1^2+\cdots p_1^{k_1})\),我们发现再把他们分别拆开再相乘就是我们所要的，为什么呢，因为这个些式子里面的因子相乘肯定也是约数。比如\(12=2^2 *3\),所以：\(约数之和:(1+2+2^2)(3+1)\).所以我们总的式子也就是\(\prod_{i=1}^{n}(1+p_i+p_i^2+\cdots+p_i^{k_i}).\)

下面是代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int mod = 1e9 + 7;
map<int, int> p;
int main()
{
    int n,i;
    cin >> n;
    ll res=1;
    ll t;
    while (n--)//这一段就是分解质因数的老套路
    {
        int x;
        cin >> x;
        for (i = 2;i <= x / i;i++)
        {
            while (x % i == 0)
            {
                x /= i;
                p[i]++;
            }
        }
        if (x > 1)
            p[x]++;
    }
//  for (auto s : p)//这个我们可以看下6的质因子就理解了
    //  cout << s.first<<" "<< s.second << endl;
    for (auto prime : p)
    {
        t = 1;
        ll a = prime.first;
        ll b = prime.second;
        while(b--)
        {
            t = (t * a + 1) % mod;//这个我们自己推两组数据就可以得到这个递推式
        }
            res = res * t % mod;
    }
    cout << res;
}