侧边栏壁纸
博主头像
GabrielxD

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

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【数学】约数个数

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

题目

870. 约数个数


给定 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

输出样例:

12

解题

方法一:数学

思路

算术基本定理,对一个正整数 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 的约数个数为:

f(n)=(α1+1)(α2+1)(αk+1)=i=1k(αi+1)\begin{aligned} f(n) &= (\alpha_1 + 1)(\alpha_2 + 1) \cdots (\alpha_k + 1) \\ &= \prod_{i=1}^{k}{(\alpha_i + 1)} \end{aligned}

证明:
nn 的任何一个约数 dd 可以质因数分解表示为:d=p1β1×p2β1××pkβk,0βiαid = p_1^{\beta_1} \times p_2^{\beta_1} \times \cdots \times p_k^{\beta_k}, \,\,\,\,\, 0 \le \beta_i \le \alpha_i
每一项的 βi\beta_i 如果不同,那约数 dd 就一定不同(由算术基本定理可知每个数的质因数分解是唯一的)。
所以 nn 的约数与其约数每一项选择 β1βk\beta_1 \sim \beta_k 的选法是对应的,故 nn 的约数个数与选法的个数时相同的。对于 nn 的约数来说:β1\beta_1 一共有 0α10 \sim \alpha_1α1+1\alpha_1 + 1 种选法、β2\beta_2 一共有 0α20 \sim \alpha_2α2+1\alpha_2 + 1 种选法 …… βk\beta_k 一共有 0αk0 \sim \alpha_kαk+1\alpha_k + 1 种选法。根据乘法原理,一共就有 (α1+1)(α2+1)(αk+1)(\alpha_1 + 1)(\alpha_2 + 1) \cdots (\alpha_k + 1) 种选法。

本题求的是 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 cnt = 1;
        for (int v : mp.values()) {
            cnt = cnt * (v + 1) % MOD;
        }
        System.out.println(cnt);
    }
}
#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 cnt = 1L;
    for (auto& pr : mp) cnt = (cnt * (pr.second + 1)) % MOD;
    printf("%d\n", cnt);
    
    return 0;
}
0
博主关闭了所有页面的评论