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

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))的时间复杂度,值得一看

描述 每个正整数都可以分解成素数的乘积&#xff0c;例如&#xff1a;62*3、2022 *5 现在&#xff0c;给定一个正整数N&#xff0c;请按要求输出它的因数分解式。 输入描述 输入第一行&#xff0c;包含一个正整数N。约定2<N<10^12 输出描述 输出一行&#xff0c;为N…...

Stable Diffusion 3报告

报告链接&#xff1a;https://stability.ai/news/stable-diffusion-3-research-paper 文章目录 要点表现架构细节通过重新加权改善整流流量Scaling Rectified Flow Transformer Models灵活的文本编码器RF相关论文 要点 发布研究论文&#xff0c;深入探讨Stable Diffuison 3的…...

一个足球粉丝该怎么建个个人博客?

做一个个人博客第一步该怎么做&#xff1f; 好多零基础的同学们不知道怎么迈出第一步。 那么&#xff0c;就找一个现成的模板学一学呗&#xff0c;毕竟我们是高贵的Ctrl c v 工程师。 但是这样也有个问题&#xff0c;那就是&#xff0c;那些模板都&#xff0c;太&#xff01;…...

缩放算法优化步骤详解

添加链接描述 背景 假设数据存放在在unsigned char* m_pData 里面&#xff0c;宽和高分别是&#xff1a;m_nDataWidth m_nDataHeight 给定缩放比例&#xff1a;fXZoom fYZoom&#xff0c;返回缩放后的unsigned char* dataZoom 这里采用最简单的缩放算法即&#xff1a; 根据比…...

[axios]使用指南

axios使用指南 Axios 是一个基于 promise 的 HTTP 库&#xff0c;可以用在浏览器和 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个步骤 设置元素为可拖放。为了使元素可拖动&#xff0c;把 draggable 属性设置为 true 。 <img draggable"true"> 拖动什么。ondragstart 和 setData() const dragestart (ev)>{ev.dataTransfer.setData(play,ev.target.id)} …...

数据结构与算法-希尔排序

引言 在计算机科学中&#xff0c;数据结构和算法是构建高效软件系统的基石。而排序算法作为算法领域的重要组成部分&#xff0c;一直在各种应用场景中发挥着关键作用。今天我们将聚焦于一种基于插入排序的改进版本——希尔排序&#xff08;Shell Sort&#xff09;&#xff0c;深…...

蓝桥杯算法错题记录

这里写目录标题 本文还在跟新&#xff0c;最新更新时间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 库中提供了诸多用来处理图片的模块&#xff0c;可以对图片做类似于 PS&#xff08;Photoshop&#xff09; 的编辑。比如&#xff1a;改变…...

使用docker datascience-notebook进行数据分析

Jupyter/datascience-notebook 简介 jupyter/datascience-notebook 是 Docker Hub 上可用的 Docker 镜像&#xff1a;https://hub.docker.com/。该镜像提供了一个开箱即用的环境&#xff0c;用于数据科学任务&#xff0c;包括&#xff1a; Jupyter Notebook: 一个基于 Web 的…...

VR全景技术在VR看房中有哪些应用,能带来哪些好处

引言&#xff1a; 随着科技的不断发展&#xff0c;虚拟现实&#xff08;VR&#xff09;技术在房地产行业中的应用也越来越广泛。其中&#xff0c;VR全景技术在VR看房中的运用尤为突出。今天&#xff0c;让我们一起深入探讨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 要想让网络中的计算机能够互相通信&#xff0c;必须为计算机指定一个标识号&#xff0c;通过这个标识号来指定要接受数据的计算机和识别发送的计算机&#xff0c;而IP地址就是这个标识号&#xff0c;也就是设备的标识。 ip地址组成&#xff1a; ip地址分类&#xff1a;…...

第十篇 - 如何利用人工智能技术做好营销流量整形管理?(Traffic Shaping)- 我为什么要翻译介绍美国人工智能科技巨头IAB公司

IAB平台&#xff0c;使命和功能 IAB成立于1996年&#xff0c;总部位于纽约市​​​​​​​。 作为美国的人工智能科技巨头社会媒体和营销专业平台公司&#xff0c;互动广告局&#xff08;IAB- the Interactive Advertising Bureau&#xff09;自1996年成立以来&#xff0c;先…...

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在两个端点建立安全通信&#xff0c;此时这两个端点被称为IPsec对等体。安全联盟&#xff0c;即SA&#xff0c;是指通信对等体之间对某些要素的约定&#xff0c;定义了两个对等体之间要用何种安全协议、IP报文的封装方式、加密和验证算法。SA是IPsec的基…...

012集——显示高考天数倒计时——vba实现

以下代码实现高考倒计时&#xff1a; Sub 高考倒计时() 高考日期 CDate("06,07," & Year(Date)) If Date > 高考日期 Then高考日期 CDate("06-07-" & Year(Date) 1) End If 年月日 Year(Date) & "年" & Month(Date) &am…...

1.1 深度学习和神经网络

首先要说的是&#xff1a;深度学习的内容&#xff0c;真的不难。你要坚持下去。 神经网络 这就是一个神经网络。里面的白色圆圈就是神经元。神经元是其中最小的单位。 神经网络 单层神经网络&#xff1a; 感知机 &#xff08;双层神经网络&#xff09; 全连接层&#xff1a; …...

sentinel docker 基础配置学习

1&#xff1a;去官网下载 Releases alibaba/Sentinel GitHub 2&#xff1a;保存到linux 3&#xff1a;编写dockerfile FROM openjdk:8-jreLABEL authors"xxx" #第二步创建一个文件夹Z RUN mkdir /app #第三步复制jar 到app 下 COPY xxxxxx-1.8.7.jar /app/#第四…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...

spring Security对RBAC及其ABAC的支持使用

RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型&#xff0c;它将权限分配给角色&#xff0c;再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...

【Linux】Linux安装并配置RabbitMQ

目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的&#xff0c;需要先安…...

ArcPy扩展模块的使用(3)

管理工程项目 arcpy.mp模块允许用户管理布局、地图、报表、文件夹连接、视图等工程项目。例如&#xff0c;可以更新、修复或替换图层数据源&#xff0c;修改图层的符号系统&#xff0c;甚至自动在线执行共享要托管在组织中的工程项。 以下代码展示了如何更新图层的数据源&…...

深入解析光敏传感技术:嵌入式仿真平台如何重塑电子工程教学

一、光敏传感技术的物理本质与系统级实现挑战 光敏电阻作为经典的光电传感器件&#xff0c;其工作原理根植于半导体材料的光电导效应。当入射光子能量超过材料带隙宽度时&#xff0c;价带电子受激发跃迁至导带&#xff0c;形成电子-空穴对&#xff0c;导致材料电导率显著提升。…...