当前位置: 首页 > article >正文

AcWing--870.约数个数

目录

题目:

分析:

代码:


题目:

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

输入格式

第一行包含整数 n。

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

输出格式

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

数据范围

1≤n≤100,
1≤ai≤2×10^9

时/空限制

1s / 64MB

输入样例:

3
2
6
8

输出样例:

12

分析:

假设一个数 N=p1^a1·p2^a2···pk^ak(p为质数)......①

N 的任意一个约数 a=p1^b1·p2^b2···pk^bk(其中 0<=bi<=ai)......②

即 N 的任意一个约数都可以用②这种形式表示,而每一个bi的取值范围都在 0~ai 之间,并且N的任意两个约数之间,只要有一个 bi 不相同,那么这两个约数就不相同(算法基本定理)

因为 bi 的取值共有 0~ai 共 (ai+1) 个取值

所以

公式一:

N的约数个数= (a1+1)(a2+1)···(ak+1) 个

ps:int 范围内的数的约数个数最多为1500个左右。

拓展:同时还可以推出另外一个 公式

公式二:

N的约数之和=(p1^0+p1^2+···+p1^a1)·(p2^0+p2^1+···+p2^a2)···(pk^0+pk^1+···+pk^ak)

自己拆开来看看,就会发现其实就是每个约数的排列组合的和。

代码:

#include <iostream>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int N = 110, mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;

    // unordered_map 是 C++ 中的一个关联容器,它提供了一种高效的方式来维护一个由键和值组成的集合,其中每个键都是唯一的。这个容器使用哈希表来实现,因此它能够在常数时间内完成查找、插入和删除操作,这使得它比使用红黑树实现的 map 容器在某些情况下更加高效。
    unordered_map<int, int> primes; // 用于存这些数的乘积因式分解后的所有底数和指数

    // 分别分解每一个数的质因数,再累加,就可得到所有数乘积的质因数的个数
    while (n -- )
    {
        int x;
        cin >> x;

        // 第一步:分解质因数,即求x的每个质因数的个数。x=p1^a1·p2^a2···pk^ak(例如x=16,16=2*2*2*2=2^4,16由4个质因数2构成,则primes[2]=4,用哈希表存)
        for (int i = 2; i <= x / i; i ++ )
            while (x % i == 0)
            {
                x /= i;
                primes[i] ++ ;
            }

        if (x > 1) primes[x] ++ ; // x是质数的情况
    }

    // 第二步:求约数个数
    LL res = 1;
    for (auto p : primes) res = res * (p.second + 1) % mod;// 公式一:N的约数个数=(a1+1)(a2+1)···(ak+1)个

    cout << res << endl;

    return 0;
}


http://www.kler.cn/a/586917.html

相关文章:

  • Windows环境下安装部署dzzoffice+onlyoffice的私有网盘和在线协同系统
  • Java中的I/O
  • 通过qemu仿真树莓派系统调试IoT固件和程序
  • 深度解析国产推理大模型DeepSeek:从入门到本地化部署!
  • C++Primer学习(7.1 定义抽象数据类型)
  • FPGA为何要尽量减少组合逻辑的使用
  • 人工智能与人的智能,改变一生的思维模型【8】逆向思维
  • 国家网络安全事件应急预案
  • DC-6靶机详解
  • Vue3 Pinia $subscribe localStorage的用法 Store的组合式写法
  • 基于变分推理与 Best‑of‑N 策略的元 Prompt 自动生成与优化框架
  • 《Python实战进阶》No24: PyAutoGUI 实现桌面自动化
  • Spring Cloud LoadBalancer 原理与实践
  • unity基础——线段与拖尾
  • 二叉树_4_面试题汇总
  • Spring Security vs Shiro vs Sa-Token
  • STM32U575RIT6单片机(一)
  • 利用Selenium和PhantomJS提升网页内容抓取与分析的效率
  • DataWhale大语言模型-大模型技术基础
  • prometheus-helm的使用