$$\color{Red}{约数之和:两种语言}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

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

输入格式

第一行包含整数 n。

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

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

数据范围

1 ≤ n ≤ 100

1 ≤ ai ≤ 2 × 10^9

输入样例：

3
2
6
8

输出样例：

252

证明

基于算数基本定理，一个数字肯定能被表示成它所有的质因数的幂次方的乘积。

而这个表示形式的质因数称之为底数，幂次称之为指数。

N = a1 ^ x1 * a2 ^ x2 * '''''' * an ^ xn

约数个数

综上所述，一个数的约数，可以被表示成它所有质因数固定底数，而指数从0 - > 最大值任选的排列组合。

那么约数个数就是组合个数，即

(1 + x1)(1 + x2)* '''' * (1 + xn)

约数之和

综合前面可知，约数和就是把所有的可以被质因数乘积再任选指数的情况，再进行求和的值。

(a1 ^ 0 + a1 ^ 2 + '''' + a1 ^ x1) *
(a2 ^ 0 + a2 ^ 2 + '''' + a2 ^ x2) * ''''(省略号)
(an ^ 0 + an ^ 2 + '''' + an ^ xn)

展开可轻松判别就是约数的和。

我们这里让t = 1，进行b次的累乘 ： t = (t * a + 1),本质上等同于：

t = 1
t = 1 + a
t = 1 + a + a ^ 2
t = 1 + a + a ^ 2 + a ^ 3 ''''''

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
    static int n, mod = (int) 1e9 + 7;
    static Map<Integer, Integer> map = new HashMap<>();
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        while (n -- > 0) {
            int x = Integer.parseInt(br.readLine());
            for (int i = 2; i <= x / i; i++) {
                while (x % i == 0) {
                    map.put(i, map.getOrDefault(i, 0) + 1);
                    x /= i;
                }
            }
            if (x > 1) map.put(x, map.getOrDefault(x, 0) + 1);
        }
        long res = 1;
        for (Integer a : map.keySet()) {
            int b = map.get(a);
            long t = 1;
            while (b -- > 0) t = (t * a + 1) % mod;
            res = res * t % mod;
        }
        System.out.println(res);
    }
}

c++

#include <unordered_map>
#include <iostream>

using namespace std;
const int mod = 1e9 + 7;
typedef long long LL;


int main()
{
    int n;
    cin >> n;
    unordered_map <int,int> cnt;

    while(n--)
    {
        int x;
        scanf("%d", &x);
        for(int i = 2; i <= x / i; i ++)
            while(x % i == 0)   cnt[i] ++, x/=i;
        if(x > 1) cnt[x] ++;
    }

    LL res = 1;
    for(auto i : cnt)   
    {
        int a = i.first, b = i.second;
        LL t = 1;
        while(b--)  t = (t * a + 1) % mod;
        res = res * t % mod;
    }

    cout << res;
    return 0;
}