算法笔试-编程练习-好题-03

这是一道非常综合的质数类的题目,值得仔细理解。


题目描述

n个正整数ai,希望你求出这些数的阶乘全部乘在一起生成的大数有多少个因子

输入描述

第一行输入一个正整数n。

第二行输入n个正整数ai​,用空格隔开

1≤n≤2×10^5

1≤ai≤10^6

输出描述

一个整数,代表这个乘积的因子数量,由于答案可能过大,请对10^9+7取模.

样例

输入

3
1 2 3

输出

6

说明

1!*2!*3!=12,共有1,2,3,4,6,12六个因子。

题目分析

【题目类型:寻找素数、因数分解、动态规划】

这是质因数分解类题目比较综合的一道,我们首先来理解题意:求1!*2!*3!=12有多少个因数。每个合数都可以被描述为若干质数次方的乘积,例如:12 = 2^2*3^1,那么如何求因子数量呢?

对于2我们有3种取法,取0个,1个和2个,对于3我们有2种取法,0个和1个,因此12共有3*2个因子,也就是指数+1的累乘,也就是(2+1)*(1+1)。

有了这样的公式我们的思路就清晰了:找到最终大数的每个质因数的指数。

因为大数是通过阶乘求得的,那么必定很多数字会被乘很多次,所以直觉上我们需要先统计每个数字使用的次数,阶乘描述的是1-n的连城,也就是1-n之间所有数字的使用次数+1。对于这种对于指定区间同时+上一个数字的操作,我们可以使用【差分数组】,用O(1)的时复杂度实现。最后用O(n)的时间复杂度复原(详见代码)。

有了每个数字的使用频次,接下来我们就希望找到每个数字的质因数及其指数。逐一分解时间复杂度过高,我们可以首先计算出指定区间内全部的指数(详见代码)。

再通过遍历质数的方式统计每个数字对该质数的指数,这里可以使用动态规划进行加速,我们假设数字i是指数p的倍数,那么 power[i] = power[i//p] +1(详见代码)。

我们遍历所有数字,累加(数字使用的频次*其质因数的指数),得到的结果就可以带回最初的公式中了。

【注意】除了上述算法外,python还有一个小细节需要注意,就是 ans = ans*(cnt+1) % mod这句话,不要写成ans *= (cnt+1) % mod,这样的写法会导致ans事实上没有被取模,从而导致涉及到大数乘法,计算速度变慢。

代码:

mod = 10**9 +7n = int(input())
arr = list(map(int, input().split()))
max_num = max(arr)# 用【查分数组--每次更新O(1)时间复杂度】统计每个数字被乘的次数
pre = [0]*(max_num+2)
for a in arr:pre[1] += 1pre[a+1] -= 1
for i in range(1, max_num+1):pre[i] += pre[i-1]# 【埃式筛选素数】
primes = [2]
is_prime = [True] * (max_num+1)
p = 3
while p <= max_num:if is_prime[p]:primes.append(p)for i in range(p*p, max_num+1, p):is_prime[i] = Falsep += 2# 统计每个素因数次方(对于整体阶乘积),同时计算因数的数量
ans = 1
for p in primes:cnt = 0power = [0]*(max_num+1)for i in range(p, max_num+1, p):power[i] = power[i//p] + 1cnt += pre[i]*power[i]if cnt != 0:ans = ans*(cnt+1) % mod
print(ans % mod)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/416153.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

IP地址存在的意义及更改方法探析

在互联网的广阔天地中&#xff0c;‌每一个连接的设备都拥有一个独特的身份标识——IP地址。‌它不仅是设备在网络中的“身份证”&#xff0c;‌更是确保数据传输准确无误的基石。‌然而&#xff0c;‌随着网络环境的不断变化&#xff0c;‌有时我们需要更改设备的IP地址以适应…

关于SpringMVC的理解

1、SpringMVC 应用 1.1、简介 1.1.1、MVC 体系结构 三层架构&#xff1a; 我们的开发架构⼀般都是基于两种形式&#xff0c;⼀种是 C/S 架构&#xff0c;也就是客户端/服务器&#xff1b;另⼀种是 B/S 架构&#xff0c;也就是浏览器服务器。在 JavaEE 开发中&#xff0c;⼏乎…

2024最新PyCharm下载安装激活汉化教程!(附激活码)

激活码&#xff08;文末附带精品籽料&#xff09;&#xff1a; K384HW36OB-eyJsaWNlbnNlSWQiOiJLMzg0SFczNk9CIiwibGljZW5zZWVOYW1lIjoibWFvIHplZG9uZyIsImxpY2Vuc2VlVHlwZSI6IlBFUlNPTkFMIiwiYXNzaWduZWVOYW1lIjoiIiwiYXNzaWduZWVFbWFpbCI6IiIsImxpY2Vuc2VSZXN0cmljdGlvbiI6I…

Qt模态对话框与非模态对话框

前言 在 Qt 中&#xff0c;模态对话框和非模态对话框是两种常见的对话框类型&#xff0c;它们的主要区别在于用户与应用程序的交互方式。 正文 对话框就是指QDialog嘛。 模态对话框 (Modal Dialog) 定义: 模态对话框是指在弹出对话框期间&#xff0c;用户无法与应用程序的…

Linux的远程登录教程(超详细)

我们在进行远程登录时要用的一种协议叫SSH&#xff0c;那什么叫SSH呢&#xff1f; SSH&#xff08;Secure Shell&#xff09;是一种网络协议&#xff0c;用于在不安全的网络中提供安全的远程登录和其他网络服务。它通过加密技术确保数据在传输过程中的机密性和完整性&#xff…

Python | Leetcode Python题解之第393题UTF-8编码验证

题目&#xff1a; 题解&#xff1a; class Solution:def validUtf8(self, data: List[int]) -> bool:MASK1, MASK2 1 << 7, (1 << 7) | (1 << 6)def getBytes(num: int) -> int:if (num & MASK1) 0:return 1n, mask 0, MASK1while num & m…

如何快速采集淘宝商品数据?

无论是谁&#xff0c;如果单凭人工的方式去收集淘宝、天猫等平台的商品数据信息&#xff0c;工作量是巨大的&#xff0c;如果借助有采集软件的第三方公司操作&#xff0c;则可实现对大数据的轻松掌握&#xff0c;但是外包给第三方公司需要支付一定的费用&#xff0c;包含技术费…

【IPV6从入门到起飞】2-2 获取你的IPV6(Teredo隧道)

【IPV6从入门到起飞】2-2 获取你的IPV6&#xff08;Teredo隧道&#xff09; 1 打工人的忧伤2 Teredo介绍2.1 背景2.2 工作原理 3 Linux 服务器获取IPV63.1 安装3.2 设置开机自启动和启动3.3 开放防火墙 UDP 35443.4 查看IPV6以及ping包测试3.5 修改Teredo服务器3.6 重启服务3.7…

SpringBoot 项目集成 xxl-job

1. xxl-job 官网 https://www.xuxueli.com/xxl-job/ 2. git 拉取 xxl-job 源码 2.1 源码仓库地址 https://github.com/xuxueli/xxl-job http://gitee.com/xuxueli0323/xxl-job 2.2 git 拉取源码 git clone https://gitee.com/xuxueli0323/xxl-job.git 2.3 git拉取源码时&…

C++11重大新增特性:左值引用 右值引用 移动构造 移动赋值

C11重大新增特性&#xff1a;左值引用 & 右值引用 & 移动构造 & 移动赋值 一、右值引用和左值引用概念和区别1.1 左值 & 左值引用1.2 右值 & 右值引用 二、左值引用和右值引用对比2.1 左值引用2.1 右值引用 三、右值和右值引用诞生的意义四、移动构造 &…

【射频通信电子线路基础第一讲】射频电子线路基础绪论——射频概念、通信系统、语义通信

1. 射频与高频广义上的概念厘清 高频&#xff1a;就是频率高&#xff08;大于10K&#xff09;&#xff0c;单位一般用MHz&#xff08;兆赫&#xff09;表示。 射频&#xff1a;Radio Frequency&#xff0c;简称RF&#xff0c;300K-300G。射频就是射频电流&#xff0c;它是一种…

Java详解String 字符串类以及String内存原理、StringBuilder类、StringJoiner类(附有代码+案例)

文章目录 九.String 字符串类型9.0 String概述9.1 字符串常用方法9.2 String内存图9.2.1直接赋值9.2.2new出来 9.3字符串比较9.4 字符串遍历9.4.1 统计字符串大小写及数字9.4.2 拼接字符串9.4.3字符串反转 9.5 StringBuilder类9.5.1StringBuilder 构造方法9.5.2StringBuilder常…

es集群详解

1、基本介绍 1.1、为什么需要集群 单台 Elasticsearch 服务器提供服务&#xff0c;往往都有最大的负载能力&#xff0c;超过这个阈值&#xff0c;服务器性能就会大大降低甚至不可用&#xff0c;所以生产环境中&#xff0c;ES 一般都是运行在指定服务器集群中。 除了负载能力&…

九银十拿到大模型(LLM)offer,面试八股

金九银十拿到大模型&#xff08;LLM&#xff09;offer&#xff0c;面试八股 从事大模型的朋友在 金J九银十拿到了一份不错的offer&#xff0c;面试十几家公司&#xff0c;通过了六家。好在分享了大佬总结的大模型方向面试的常见题目&#xff08;含答案&#xff09;&#xff0c;…

RS232转RS485

1.232转485转换器 232转485转换器是RS-232与RS-485之间的双向接口的转换器&#xff0c;应用于主控机之间&#xff0c;主控机与单片机或外设之间构成点到点&#xff0c;点到多点远程多机通信网络&#xff0c;实现多机应答通信&#xff0c;广泛地应用于工业自动化控制系统&#x…

LLM代码实现-Qwen(Function Calling)

简介 Function Calling 是一种让 Chat Completion 模型调用外部函数的能力&#xff0c;可以让模型不仅仅根据自身的数据库知识进行回答&#xff0c;而是可以额外挂载一个函数库&#xff0c;然后根据用户提问去函数库检索&#xff0c;按照实际需求调用外部函数并获取函数运行结…

Unknown command: “create-react-app“

在创建react项目时出现报错" Unknown command: "create-react-app" " 解决方法&#xff1a; 配置全局变量&#xff0c;" win r " 打开cmd窗口&#xff0c;输入下列命令&#xff0c;回车等待结束即可&#xff1a; npx create-react-app my-pro…

Docker部署项目时的服务端口设置——给容器添加新端口映射

Docker给容器添加新端口映射 1 Docker安装Ubuntu22.042 创建新容器3 给容器添加端口映射3.1 查看运行的容器3.2 查看容器挂载目录3.3 停止容器3.4 停止docker服务3.5 进入容器挂载目录3.6 修改config.v2.json文件3.7 修改hostconfig.json文件3.8 启动docker3.9 启动容器 4 端口…

七款最佳的渗透测试工具(非常详细)零基础入门到精通,收藏这一篇就够了

渗透测试工具是模拟对计算机系统、网络或 Web 应用程序的网络攻击的软件应用程序&#xff0c;它们的作用是在实际攻击者之前发现安全漏洞。它们可以作为系统的压力测试&#xff0c;揭示哪些区域可能会受到真正的威胁。 本文我将介绍七款最佳的渗透测试工具。 1 Kali Linux K…

【数据结构入门】排序算法之插入排序与选择排序

目录 前言 一、排序的概念及运用 1.排序的概念 2.排序的运用 3.常见排序算法 二、插入排序与选择排序 2.1插入排序 2.1.1直接插入排序 1&#xff09;基本思想 2&#xff09;具体步骤 3&#xff09;算法特性 4&#xff09;算法实现 2.1.2希尔排序 1) 基本思想 2&…