AcWing--871.约数之和

ops/2025/3/16 13:06:18/

目录

题目:

分析:

代码:


题目:

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

输出样例:

252

分析:

见另一篇文章: AcWing--870.约数个数-CSDN博客

代码:

// 假设一个数N=p1^a1·p2^a2···pk^ak(p为质数)
// 公式一:N的约数个数=(a1+1)(a2+1)···(ak+1)个
// 公式二:N的约数之和=(p1^0+p1^2+···+p1^a1)·(p2^0+p2^1+···+p2^a2)···(pk^0+pk^1+···+pk^ak)
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>using namespace std;typedef long long LL;const int N = 110, mod = 1e9 + 7;int main()
{int n;cin >> n;unordered_map<int, int> primes;while (n -- ){int x;cin >> x;for (int i = 2; i <= x / i; i ++ )while (x % i == 0){x /= i;primes[i] ++ ;}if (x > 1) primes[x] ++ ;}LL res = 1;// 公式二:N的约数之和=(p1^0+p1^2+···+p1^a1)·(p2^0+p2^1+···+p2^a2)···(pk^0+pk^1+···+pk^ak)for (auto p : primes){LL a = p.first, b = p.second; // a为质因数(对应公式中的底数p),b为该质因数的个数(对应公式中的指数a)LL t = 1;// 求(pi^0+pi^2+···+pi^ai),数学问题hhwhile (b -- ) t = (t * a + 1) % mod; // 第一次:t=(1*a+1)=a+1。第二次:t=((a+1)*a+1)=a^2+a+1。第三次:t=((a^2+a+1)*a+1)=a^3+a^2+a+1...第i次:t=a^i+...+a^2+a+1res = res * t % mod;}cout << res << endl;return 0;
}


http://www.ppmy.cn/ops/166209.html

相关文章

【QT:信号和槽】

QT信号涉及的三要素&#xff1a;信号源、信号类型、信号的处理方式。 QT的信号槽机制&#xff1a; 给按钮的点击操作关联一个处理函数&#xff0c;用户点击按钮时触发&#xff0c;对应的处理函数就会执行 QT中使用connect函数将信号和槽关联起来&#xff0c;信号触发&#xf…

深度解析前端面试八股文:核心知识点与高效应对策略

深度解析前端面试八股文&#xff1a;核心知识点与高效应对策略 1. 引言 前端面试是每位开发者迈向职业进阶的重要环节&#xff0c;涉及 HTML、CSS、JavaScript、性能优化、浏览器原理、网络、安全、框架&#xff08;Vue/React&#xff09; 等核心知识点。本文不仅会覆盖 前端…

责任链模式的C++实现示例

核心思想 责任链模式是一种行为设计模式&#xff0c;允许多个对象都有机会处理请求&#xff0c;从而避免请求的发送者与接收者之间的耦合。请求沿着处理链传递&#xff0c;直到某个对象处理它为止。 解决的问题 ​解耦请求发送者与处理者&#xff1a;请求的发送者无需知道具…

【ESP32】ESP-IDF开发 | 经典蓝牙开发 | 蓝牙串口协议(SPP) + 客户端和服务端例程

1. 简介 相信我们最早接触蓝牙&#xff0c;就是在某宝上买一个小巧的蓝牙模块&#xff0c;接到单片机上&#xff0c;通过AT指令进行简单配置&#xff0c;就可以用手机连接该模块&#xff0c;然后远程发送信息给单片机。这里面用到的就是SPP协议&#xff08;Serial Port Protoco…

Python中很常用的100个函数整理

Python 内置函数提供了强大的工具&#xff0c;涵盖数据处理、数学运算、迭代控制、类型转换等。本文总结了 100 个常用内置函数&#xff0c;并配备示例代码&#xff0c;提高编程效率。 1. abs() 取绝对值 print(abs(-10)) # 10 2. all() 判断所有元素是否为真 print(all([…

【2025】基于python+django的慢性病健康管理系统(源码、万字文档、图文修改、调试答疑)

系统功能结构图如下 慢性病健康管理系统 课题背景 随着全球人口老龄化的加剧以及生活方式的改变&#xff0c;慢性病的发病率呈上升趋势&#xff0c;给个人健康和社会医疗资源带来了巨大压力。传统的慢性病管理模式存在信息不畅、患者参与度低、医疗资源分配不均等问题&#xf…

如何利用物理按键控制LVGL控件的大小与状态

​ lvgl可以利用物理按键控制控件的选择和状态&#xff0c;演示视频如下&#xff1a; 单物理按键控制LVGL控件的选择和状态 移植方法如下&#xff1a;1 在注册设备中&#xff0c;填写对应的变量和初始化函数。这里我们以移keypad为例&#xff0c;因为keypad的功能很多。 ![请添…

使用Fluent-bit将容器标准输入和输出的日志发送到Kafka

什么是fluent-bit&#xff1f; Fluent Bit 是一款开源的轻量级日志处理器与转发器&#xff0c;专为嵌入式系统、容器化环境及分布式架构设计。其核心功能包括日志收集、过滤、聚合和传输&#xff0c;支持多种输入源&#xff08;如文件、系统日志、HTTP接口&#xff09;和输出目…