GESP5级T1真题 [202309] 因数分解——O(sqrt(n))的时间复杂度,值得一看
描述
每个正整数都可以分解成素数的乘积,例如:6=2*3、20=22 *5
现在,给定一个正整数N,请按要求输出它的因数分解式。
输入描述
输入第一行,包含一个正整数N。约定2<=N<=10^12
输出描述
输出一行,为N的因数分解式。要求按质因数由小到大排列,乘号用星号*表示,且左右各空一格。当且仅当一个素数出现多次时,将它们合并为指数形式,用上箭头^表示,且左右不空格。
用例输入 1
6
用例输出 1
2 * 3
用例输入 2
20
用例输出 2
2^2 * 5
用例输入 3
23
用例输出 3
23
来源
GESP 五级
这道题就算用O(n)的方法也过不了,所以要用O(sqrt(n)),这道题的关键就是在这里。
众所周知,i*i<=n就是sqrt(n)的时间复杂度,那我们就要在其基础上写代码
ACcode
#include <bits/stdc++.h>
using namespace std;long long n;
bool flag=false,f2;
int main() {cin>>n;for (int i=2;i*i<=n;i++){if (n%i==0){f2=1;int cnt=0;while (n%i==0) n/=i, cnt++;//O(sqrt(n))+O(log2n)=O(sqrt(n))if (flag==false){flag=true;}else cout<<" * ";if (cnt>1){cout<<i<<"^"<<cnt;}else cout<<i;}}if(f2==0){cout<<n;}else if(n!=1)cout<<" * "<<n;return 0;
}
感谢王大佬提供思路
看了这么久,作者也写了这么久,能不能点一个赞,在收藏一下呢?最好的话在点个关注吧
谢谢啦!

相关文章:
GESP5级T1真题 [202309] 因数分解——O(sqrt(n))的时间复杂度,值得一看
描述 每个正整数都可以分解成素数的乘积,例如:62*3、2022 *5 现在,给定一个正整数N,请按要求输出它的因数分解式。 输入描述 输入第一行,包含一个正整数N。约定2<N<10^12 输出描述 输出一行,为N…...
Stable Diffusion 3报告
报告链接:https://stability.ai/news/stable-diffusion-3-research-paper 文章目录 要点表现架构细节通过重新加权改善整流流量Scaling Rectified Flow Transformer Models灵活的文本编码器RF相关论文 要点 发布研究论文,深入探讨Stable Diffuison 3的…...
一个足球粉丝该怎么建个个人博客?
做一个个人博客第一步该怎么做? 好多零基础的同学们不知道怎么迈出第一步。 那么,就找一个现成的模板学一学呗,毕竟我们是高贵的Ctrl c v 工程师。 但是这样也有个问题,那就是,那些模板都,太!…...
缩放算法优化步骤详解
添加链接描述 背景 假设数据存放在在unsigned char* m_pData 里面,宽和高分别是:m_nDataWidth m_nDataHeight 给定缩放比例:fXZoom fYZoom,返回缩放后的unsigned char* dataZoom 这里采用最简单的缩放算法即: 根据比…...
[axios]使用指南
axios使用指南 Axios 是一个基于 promise 的 HTTP 库,可以用在浏览器和 node.js 中。 axios 安装 npm安装 $ npm install axios 使用cdn <script src"https://unpkg.com/axios/dist/axios.min.js"></script> axios API axios(config)…...
HTML5基础2
drag 可以把拖放事件拆分成4个步骤 设置元素为可拖放。为了使元素可拖动,把 draggable 属性设置为 true 。 <img draggable"true"> 拖动什么。ondragstart 和 setData() const dragestart (ev)>{ev.dataTransfer.setData(play,ev.target.id)} …...
数据结构与算法-希尔排序
引言 在计算机科学中,数据结构和算法是构建高效软件系统的基石。而排序算法作为算法领域的重要组成部分,一直在各种应用场景中发挥着关键作用。今天我们将聚焦于一种基于插入排序的改进版本——希尔排序(Shell Sort),深…...
蓝桥杯算法错题记录
这里写目录标题 本文还在跟新,最新更新时间24/3/91. nextInt () next() nextLine() 的注意事项2 . 转换数据类型int ,string,charint -> string , charstring -> int ,charchar -> int , string 进制转换十六进制转化为10 进制 最大公约数 本文还在跟新&am…...
【Python 图像处理 PIL 系列 13 -- PIL 及 Image.convert 函数介绍】
文章目录 Python PIL 介绍PIL 使用介绍PIL convert 介绍PIL convert 使用示例 Python PIL 介绍 PIL 是 Python Image Library 的简称。PIL 库中提供了诸多用来处理图片的模块,可以对图片做类似于 PS(Photoshop) 的编辑。比如:改变…...
使用docker datascience-notebook进行数据分析
Jupyter/datascience-notebook 简介 jupyter/datascience-notebook 是 Docker Hub 上可用的 Docker 镜像:https://hub.docker.com/。该镜像提供了一个开箱即用的环境,用于数据科学任务,包括: Jupyter Notebook: 一个基于 Web 的…...
VR全景技术在VR看房中有哪些应用,能带来哪些好处
引言: 随着科技的不断发展,虚拟现实(VR)技术在房地产行业中的应用也越来越广泛。其中,VR全景技术在VR看房中的运用尤为突出。今天,让我们一起深入探讨VR全景技术在VR看房中的应用及其带来的种种好处。 一、…...
Winform窗体随着屏幕的DPI缩放,会引起窗体变形及字体变形,superTabControl标签字体大小不匹配
一、前言 superTabControl做的浏览器标签(cefsharp)在缩放比例(125%,150%时字体不协调) 物联网浏览器,定制浏览器,多媒体浏览器(支持H264)参考栏目文章即可 二、配置参数 app.manifest参数 dpiAware =true <application xmlns="urn:schemas-microsoft-c…...
java网络编程 01 IP,端口,域名,TCP/UDP, InetAddress
01.IP 要想让网络中的计算机能够互相通信,必须为计算机指定一个标识号,通过这个标识号来指定要接受数据的计算机和识别发送的计算机,而IP地址就是这个标识号,也就是设备的标识。 ip地址组成: ip地址分类:…...
第十篇 - 如何利用人工智能技术做好营销流量整形管理?(Traffic Shaping)- 我为什么要翻译介绍美国人工智能科技巨头IAB公司
IAB平台,使命和功能 IAB成立于1996年,总部位于纽约市。 作为美国的人工智能科技巨头社会媒体和营销专业平台公司,互动广告局(IAB- the Interactive Advertising Bureau)自1996年成立以来,先…...
npm ERR! errno -13具体问题处理
npm ERR! errno -13具体问题处理 出现问题的报错 npm ERR! code EACCES npm ERR! syscall open npm ERR! path /Users/xxxx/.npm/_cache/index-v5/c6/06/xxxxx npm ERR! errno -13 npm ERR! npm ERR! Your cache folder contains root-owned files, due to a bug in npm ERR! …...
【Python】3. 基础语法(2) -- 语句篇
顺序语句 默认情况下, Python 的代码执行顺序是按照从上到下的顺序, 依次执行的. print("1") print("2") print("3")执行结果一定为 “123”, 而不会出现 “321” 或者 “132” 等. 这种按照顺序执行的代码, 我们称为 顺序语句. 这个顺序是很关…...
IPsec VPN之安全联盟
一、何为安全联盟 IPsec在两个端点建立安全通信,此时这两个端点被称为IPsec对等体。安全联盟,即SA,是指通信对等体之间对某些要素的约定,定义了两个对等体之间要用何种安全协议、IP报文的封装方式、加密和验证算法。SA是IPsec的基…...
012集——显示高考天数倒计时——vba实现
以下代码实现高考倒计时: Sub 高考倒计时() 高考日期 CDate("06,07," & Year(Date)) If Date > 高考日期 Then高考日期 CDate("06-07-" & Year(Date) 1) End If 年月日 Year(Date) & "年" & Month(Date) &am…...
1.1 深度学习和神经网络
首先要说的是:深度学习的内容,真的不难。你要坚持下去。 神经网络 这就是一个神经网络。里面的白色圆圈就是神经元。神经元是其中最小的单位。 神经网络 单层神经网络: 感知机 (双层神经网络) 全连接层: …...
sentinel docker 基础配置学习
1:去官网下载 Releases alibaba/Sentinel GitHub 2:保存到linux 3:编写dockerfile FROM openjdk:8-jreLABEL authors"xxx" #第二步创建一个文件夹Z RUN mkdir /app #第三步复制jar 到app 下 COPY xxxxxx-1.8.7.jar /app/#第四…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...
RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...
