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

题解:ABC276D - Divide by 2 or 3

题解:ABC276D - Divide by 2 or 3

·题目

链接:Atcoder。

链接:洛谷。

·难度

算法难度:入门。

思维难度:入门。

调码难度:入门。

综合评价:极简。

·算法

数论。

·思路

由大脑可知,最后得到的相等的数一定是所有数的gcd,所以先求出所有数的gcd,之后依次遍历每一个数,求出该数能否除以2、3变成gcd(如果不能直接输出-1退出程序,否则继续做),以及若能变成gcd一共要除多少次(加到ans里)。若没有中途退出,就把ans输出。

·代价

O(n),A掉。

·细节

实现gcd时可以定义一个g记录,先输入a[1],把g设成a[1],之后通过辗转相除法求出所有数的观察到。

对于上文中提到的两个问题,我们可以对a[i]与g作商,并把该数反复除以2、3直到无法整除或已经除到1,如果是无法整除,就说明无法完成任务,否则把除的次数加到ans里。

·代码

#include<bits/stdc++.h>
#define N 1100
using namespace std;
int a[N]={},g=0,ans=0,n=0;
int gcd(int a,int b);
int main(){scanf("%d%d",&n,&a[1]);g=a[1];for(int i=2;i<=n;i++){scanf("%d",&a[i]);g=gcd(g,a[i]);}for(int i=1;i<=n;i++){int tmp=a[i]/g;while(tmp>1&&tmp%2==0){tmp/=2;ans++;}while(tmp>1&&tmp%3==0){tmp/=3;ans++;}if(tmp!=1){printf("-1\n");return 0;}}printf("%d\n",ans);return 0;
}
int gcd(int a,int b){if(a<b){return gcd(b,a);}if(b==0){return a;}return gcd(b,a%b);
}

·注意

gcd千万不要把初始值设置成1,再和每个数运算,否则会直接WA掉。

相关文章:

题解:ABC276D - Divide by 2 or 3

题解&#xff1a;ABC276D - Divide by 2 or 3 题目 链接&#xff1a;Atcoder。 链接&#xff1a;洛谷。 难度 算法难度&#xff1a;入门。 思维难度&#xff1a;入门。 调码难度&#xff1a;入门。 综合评价&#xff1a;极简。 算法 数论。 思路 由大脑可知&#x…...

后台管理系统

1.1 项目概述 简易后台管理系统是一个基于Vue3ElemrntPlus的后台管理系统&#xff0c;提供了用户登录、记住密码、数据的增删改查、分页、错误信息提示等功能&#xff0c;旨在协助管理员对特定数据进行管理和操作。 没有后台对接&#xff0c;数据源为假数据。 全部代码已上传G…...

C++数据结构之平衡二叉搜索树(一)——AVL的实现(zig与zag/左右双旋/3+4重构)

本文目录 00.BBST——平衡二叉搜索树01.AVL树02.AVL的插入2.1单旋——zig 与 zag2.2插入节点后的单旋实例2.3手玩小样例2.4双旋实例2.5小结 03.AVL的删除3.1单旋删除3.2双旋删除3.3小结 04.34重构05.综合评价AVL5.1优点5.2缺点 06.代码注意插入算法删除算法完整代码&#xff1a…...

静态库和动态库

库文件 库文件是计算机上的一类文件&#xff0c;可以简单的把库文件看成一种代码仓库&#xff0c;它提供给使用者一些可以直接拿来用的变量、函数或类。 库是特殊的一种程序&#xff0c;编写库的程序和编写一般的程序区别不大&#xff0c;只是库不能单独运行。库文件有两种&a…...

用于Voronoi图构建的Fortune算法的C++实现

Voronoi图是一种在计算几何中广泛使用的数据结构&#xff0c;它可以用于解决最近邻搜索、路径规划等问题。在这篇文章中&#xff0c;我们将探讨一种用于构建Voronoi图的高效算法——Fortune算法&#xff0c;并提供其C实现。 一、Voronoi图简介 Voronoi图是由一组点在平面上生…...

笔记汇总 | 斯坦福 CS229 机器学习

文章目录 前言课程参考文章推荐阅读 前言 本文为斯坦福大学 CS229 机器学习课程学习笔记 本文主体部分转载自黄海广博士&#xff0c;文末已给出链接&#xff0c;大家有兴趣可以直接访问笔记首页&#xff0c;下载对应课程资料及作业代码 课程官网&#xff1a;CS229: Machine …...

git 版本管理工具 学习笔记

git 学习笔记 目录 一、git是什么 二、创建仓库 三、工作区域和文件状态 四、添加和提交文件 五、回退版本 &#xff08;了解&#xff09; 六、查看差异 七、删除文件 八、.gitignore文件&#xff08;了解&#xff09; 九、github ssh-key配置 十、本地仓库和远程仓库内…...

Bean基本注解开发和Bean依赖注入注解开发

目录 1.Bean基本注解开发 Component Scorelazy PostConstruct和PreDestroy RepositoryServiceController 2.Bean依赖注入注解开发 Value Autowired Qualifier Resource 扩展AutoWired 1.Bean基本注解开发 基本Bean注解&#xff0c;主要是使用注释的方式替代原有xml的…...

使用IIS服务器搭建一个网站

参考文章 使用IIS&#xff08;Internet Information Services&#xff09;服务器搭建一个网站相对来说是比较简单的。以下是基本的步骤&#xff1a; 安装IIS&#xff1a; 首先&#xff0c;确保你的操作系统已经安装了IIS。在大多数Windows版本中&#xff0c;IIS都是可选安装项…...

HCIP 三层交换机

一、实现VLAN间通信 在传统的交换机组网中&#xff0c;默认所有网络都处于同一个广播域&#xff0c;带来了许多问题&#xff0c;VLAN技术的提出&#xff0c;满足了二层组网隔离广播域需求&#xff0c;使得属于不同的VLAN间网络无法通信&#xff0c;但不同VLAN之间又存在着互相…...

利用python 进行数据分析(第三版)第二章小结

利用python 进行数据分析&#xff08;第三版&#xff09;第二章小结 由于是闲暇时间看的&#xff0c;且为读书笔记&#xff0c;所以只会写一些心得和容易混淆的知识&#xff0c;简单知识将不在重复 在变量或者函数后使用?可以查看详细信息。?还有最后一个用途&#xff0c;即…...

【ASP.NET MVC】使用动软(四)(12)

一、筛选器类和Cookie实现路由 需解决的问题&#xff1a; 网站登录往往需要用户名密码验证&#xff0c;为避免重复验证&#xff0c;一般采用Cookie 、Session等技术来保持用户的登录状态&#xff1a; Session是在服务端保存的一个数据结构&#xff0c;用来跟踪用户的状态&…...

【web逆向】全报文加密及其登录流程的分析案例

aHR0cHM6Ly9oZWFsdGguZWxkZXIuY2NiLmNvbS9zaWduX2luLw 涉及加密库jsencrypt 定位加密点 先看加密的请求和响应&#xff1a; 全局搜索加密字段jsondata&#xff0c;这种非特定参数的一般一搜一个准&#xff0c;搜到就是断点。起初下的断点没停住&#xff0c;转而从调用栈单步…...

MyBatis枚举映射类讨论

前言 本篇需要对于MyBatis有一定的认识&#xff0c;而且只是针对于TypeHandler接口来讨论&#xff0c;暂不讨论其他方面的问题 TypeHandler概叙 TypeHandler是MyBatis设计的一个用于参数的接口&#xff0c;你们会不会很好奇MyBatis是如何把整形&#xff0c;时间&#xff0c;字符…...

微信开发之朋友圈自动点赞的技术实现

简要描述&#xff1a; 朋友圈点赞 请求URL&#xff1a; http://域名地址/snsPraise 请求方式&#xff1a; POST 请求头Headers&#xff1a; Content-Type&#xff1a;application/jsonAuthorization&#xff1a;login接口返回 参数&#xff1a; 参数名必选类型说明wId…...

Linux命令200例:sed对文本进行修改、替换和删除等操作的强大工具(常用)

&#x1f3c6;作者简介&#xff0c;黑夜开发者&#xff0c;全栈领域新星创作者✌。CSDN专家博主&#xff0c;阿里云社区专家博主&#xff0c;2023年6月csdn上海赛道top4。 &#x1f3c6;数年电商行业从业经验&#xff0c;历任核心研发工程师&#xff0c;项目技术负责人。 &…...

python 合并多个excel文件

使用 openpyxl 思路&#xff1a; 读取n个excel的文件&#xff0c;存储在一个二维数组中&#xff0c;注意需要转置。将二维数组的数据写入excel。 安装软件&#xff1a; pip install openpyxl源代码&#xff1a; import os import openpyxl # 将n个excel文件数据合并到一个…...

【Docker】性能测试监控平台搭建:InfluxDB+Grafana+Jmeter+cAdvisor

前言 在做性能测试时&#xff0c;如果有一个性能测试结果实时展示的页面&#xff0c;可以极大的提高我们对系统性能表现的掌握程度&#xff0c;进而提高我们的测试效率。但是我们每次打开Jmeter都会有几个硕大的字提示别用GUI模式进行负载测试&#xff0c;而且它自带的监视器效…...

wordpress日主题Ripro9.0最新二开修正源码下载+美化包和插件

日主题Ripro9.0最新二开升级修正源码美化包和插件&#xff0c;RiPro9.0的二开版本新模板&#xff0c;包含2个美化包和全屏水印以及防复制插件。 模板和美化包路径:\wp-content\themes 插件路径&#xff1a;\wp-content\plugins&#xff0c;有兴趣的自行去体验吧...

fib Model Code史海拾贝

文章目录 0. 背景1. 强度等级不一致&#xff08;20230807&#xff09;1.1 问题描述&#xff08;20230807&#xff09;1.2 问题探索 0. 背景 本文主要记录在学习了解ModelCode的过程中产生的问题。当然&#xff0c;主要是我个人认为有意思的地方。欢迎有共同兴趣的网友留言一起…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...

[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG

TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码&#xff1a;HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...

数据结构:递归的种类(Types of Recursion)

目录 尾递归&#xff08;Tail Recursion&#xff09; 什么是 Loop&#xff08;循环&#xff09;&#xff1f; 复杂度分析 头递归&#xff08;Head Recursion&#xff09; 树形递归&#xff08;Tree Recursion&#xff09; 线性递归&#xff08;Linear Recursion&#xff09;…...

FFmpeg avformat_open_input函数分析

函数内部的总体流程如下&#xff1a; avformat_open_input 精简后的代码如下&#xff1a; int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...

算法250609 高精度

加法 #include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> using namespace std; char input1[205]; char input2[205]; int main(){while(scanf("%s%s",input1,input2)!EOF){int a[205]…...