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/#第四…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...
Windows安装Miniconda
一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...
提升移动端网页调试效率:WebDebugX 与常见工具组合实践
在日常移动端开发中,网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时,开发者迫切需要一套高效、可靠且跨平台的调试方案。过去,我们或多或少使用过 Chrome DevTools、Remote Debug…...
tauri项目,如何在rust端读取电脑环境变量
如果想在前端通过调用来获取环境变量的值,可以通过标准的依赖: std::env::var(name).ok() 想在前端通过调用来获取,可以写一个command函数: #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...
