侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【数学】约数之和

GabrielxD
2022-12-02 / 0 评论 / 0 点赞 / 42 阅读 / 1,104 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-12-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

871. 约数之和


给定 nn 个正整数 aia_i ,请你输出这些数的乘积的约数之和,答案对 109+710^9+7 取模。

输入格式

第一行包含整数 nn

接下来 nn 行,每行包含一个整数 aia_i

输出格式

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

数据范围

1n1001 \le n \le 100 ,
1ai2×1091 \le a_i \le 2 \times 10^9

输入样例:

3
2
6
8

输出样例:

252

解题

方法一:数学

思路

算术基本定理,对一个正整数 nn 进行分解质因数:n=i=1kpiαi=p1α1×p2α2××pkαkn = \prod_{i=1}^{k}{p_i^{\alpha_i}} = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \cdots \times p_k^{\alpha_k}

那么 nn 的约数之和为:

σ(n)=(p10+p11+p12++p1α1)(p20+p21+p22++p2α2)(pk0+pk1+pk12++pkαk)=i=1k(j=0αkpij)\begin{aligned} \sigma(n) &= (p_1^0+p_1^1+p_1^2+ \cdots + p_1^{\alpha_1})(p_2^0+p_2^1+p_2^2+ \cdots + p_2^{\alpha_2}) \cdots (p_k^0+p_k^1+p_k1^2+ \cdots + p_k^{\alpha_k}) \\ &= \prod_{i=1}^{k}{(\sum_{j=0}^{\alpha_k}{p_i^j})} \end{aligned}

证明:
nn 的质因数 p1α1p_1^{\alpha_1} 的约数为:p10,p11,p12,,p1α1p_1^0, p_1^1, p_1^2, \cdots, p_1^{\alpha_1} ,那么同理, pkαkp_k^{\alpha_k} 的约数为:pk0,pk1,pk2,,pkαkp_k^0, p_k^1, p_k^2, \cdots, p_k^{\alpha_k}
实际上 nn 的约数是在 p1α1,p12α2,,pkαkp_1^{\alpha_1}, p_12^{\alpha_2}, \cdots, p_k^{\alpha_k} 每一个点约数中分别挑一个相乘得来的,所以一共有约数个数种挑法,由乘法原理算出它们的和为:(p10+p11+p12++p1α1)(p20+p21+p22++p2α2)(pk0+pk1+pk12++pkαk)(p_1^0+p_1^1+p_1^2+ \cdots + p_1^{\alpha_1})(p_2^0+p_2^1+p_2^2+ \cdots + p_2^{\alpha_2}) \cdots (p_k^0+p_k^1+p_k1^2+ \cdots + p_k^{\alpha_k})

本题求的是 nn 个数乘在一起的约数之和,具体做法是:把每个数都分别做质因数分解,统计并累和每个质因子的指数,然后根据上面给出的公式算出约数之和。

分解质因数的做法见:【数学】分解质因数

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int MOD = (int) 1e9 + 7;
    static Map<Integer, Integer> mp;
    
    static void pf(int n) {
        for (int i = 2; i <= n / i; ++i) {
            if (n % i == 0) {
                int s = 0;
                while (n % i == 0) {
                    n /= i;
                    ++s;
                }
                mp.put(i, mp.getOrDefault(i, 0) + s);
            }
        }
        if (n > 1) mp.put(n, mp.getOrDefault(n, 0) + 1);
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        mp = new HashMap<>();
        while (n-- > 0) {
            in.nextToken();
            pf((int) in.nval);
        }
        long sum = 1L;
        for (Map.Entry<Integer, Integer> entry : mp.entrySet()) {
            int p = entry.getKey(), a = entry.getValue();
            long tmp = 1L;
            while (a-- > 0) tmp = (tmp * p + 1) % MOD;
            sum = sum * tmp % MOD;
        }
        System.out.println(sum);
    }
}
#include <iostream>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int MOD = 1e9 + 7;
unordered_map<int, int> mp;

void pf(int n) {
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            int s = 0;
            while (n % i == 0) {
                n /= i;
                ++s;
            }
            mp[i] += s;
        }
    }
    if (n > 1) ++mp[n];
}

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        int a;
        scanf("%d", &a);
        pf(a);
    }
    LL sum = 1L;
    for (auto& pr : mp) {
        int p = pr.first, a = pr.second;
        LL tmp = 1L;
        while (a--) tmp = (tmp * p + 1) % MOD;
        sum = (sum * tmp) % MOD;
    }
    printf("%d\n", sum);
    
    return 0;
}
0

评论区