约数之和

原题链接：871. 约数之和 - AcWing题库

解题思路

通过算术基本定理——任何一个大于1的自然数可以分解成一些质数的乘积。且表示方式唯一。

n = p1^c1 * p2*c2 * … （p1,p2…是n的质因子）

而n的约数是也是由n的质因子的乘积，但是指数<=在n中的质数c

所以n约数之和用乘法分配率可以转化为 (p1^0 + p1^1 + … + p1^c1) * (p2^0 + p2^2 + … + p2^c2) + …

接下来的问题是求(p1^0 + p1^1 + … + p1^c1)：

我们可以这样求——(p1 + 1) * p1 + 1= p1^2 + p1^1 + 1 = p1^2 + p1^1 + p1^0

（p1^2 + p1^1 + 1）* p1 + 1 = p1^3 + p1^2 + p1^1 + 1

以此类推就可以求出(p1^0 + p1^1 + … + p1^c1)

源代码

#include <iostream>
#include <cstdio>
#include <unordered_map>

using namespace std;

const int mod = 1e9 + 7;

int main()
{
    unordered_map<int,int> hash;//存储质因子的哈希表
    int n;
    cin >> n;
    for(int x = 0;x < n;x ++)
    {
        int a;
        scanf("%d",&a);
        int b = a;
        for(int i = 2;i <= a / i;i ++)
        {
            while(b % i == 0)
            {
                b /= i;
                hash[i] ++;
            }
        }
        if(b > 1)hash[b] ++;
    }
    int re = 1;
    for(auto i : hash)
    {
        long long a = i.first;
        long long b = i.second;
        long long t = 1;
        for(int i = 0;i < b;i ++)//求约数之和
        {
            t = (t * a + 1) % mod;
        }
        re = re * t % mod;
    }
    cout << re; 
    return 0;
}