程序员经验分享-hwhale

luogu p2651 添加括号Ⅲ

2023-05-16

题目描述

现在给出一个表达式，形如a1/a2/a3/.../an

如果直接计算，就是一个个除过去，比如1/2/1/4=1/8。

然而小A看到一个分数感觉很不舒服，希望通过添加一些括号使其变成一个整数。一种可行的办法是(1/2)/(1/4)=2。

现在给出这个表达式，求问是否可以通过添加一些括号改变运算顺序使其成为一个整数。

输入输出格式

输入格式：

 

一个测试点中会有多个表达式。

第一行t，表示表达式数量。

对于每个表达式，第一行是n，第二行n个数，第i个数表示ai。

 

输出格式：

 

输出t行。

对于每个表达式，如果可以通过添加括号改变顺序使其变成整数，那么输出“Yes”，否则输出“No”

 

输入输出样例

输入样例#1： 

2
4
1 2 1 4
5
6 5 7 9 12
输出样例#1： 

Yes
No

说明

对于40%的数据，n<=16

对于70%的数据，n<=100

对于全部数据，2<=n<=10000，1<=t<=100，1<=ai<=maxlongint

 

首先写成a1/a2/a3/.../an的形式

（题目中的数据已经保证了ai是正整数）

分析：通过加括号的方式使得最终分数的分子所含的所有因子包含分母上的所有因子，也就是通过约分也是是最终的分母变为1

a2一定在最终的分母上，为什么这么说呢？

对于a1/a2/a3/.../an，考虑加括号的方式：

我们可以很容易地知道，a1一定要作为分母出现，因为没有任何一个数在a1之前。所以我们就可以看作是a1去除一个数，这个数是由a2/a3/.../an通过加括号的方式算出的

现在我们要做的，就是使（a2/a3/.../an）中所含的因子数尽量少，此时已经与a1无关了。

可以证明，（a2/a3/.../an）的时候，因子是最少的：

对于（a2/a3/.../an）来说，a2作为分子，不管后面的数字如何添加括号，对于a2，只有乘这个数或是除以这个数（假设中间结果不约分）。a2每乘一个数b，因子加上(b包含的所有因子)，a2除以所有b，因子减去（b包含的所有因子），a2中不含的因子最终将加到a1上。

可以看出，（a2/a3/.../an）中间不加括号，进行连除时，a2可以在不增加新的因子情况下，因子最少，所以我们要加的括号就是这样

a1/（a2/a3/.../an）

然后如何判断能否使最终结果变为整数呢？只需要判断（a3,a4...an）这些数中是否含有a2的全部因子，具体做法：从a1扫到an,每个数（当然除了a2）分别与a2约去他们的最大公因数，an约分结束，a2能变为1，那就是能使最终结果变为整数，反之不能。

转载于:https://www.cnblogs.com/zeroform/p/7541412.html

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

luogu

P2651

添加括号

luogu p2651 添加括号Ⅲ 的相关文章

  • 【题解】洛谷P2651 添加括号III（gcd 数学）

    看到是入门难度结果看了半天也不知道啥做法 kkk大神给出了答案 xff0c a1肯定在分子上 xff0c a2肯定在分母上 xff0c 如果我们想让这个式子更有可能化成整数 xff0c 那么a1 a3 a4 an都应该在分子上 xff0c

  • 【Luogu P1661】扩散

    题目 xff1a 一个点每过一个单位时间就会向四个方向扩散一个距离 xff0c 如图 两个点 a b 连通 xff0c 记作 e a b 当且仅当 a b 的扩散区域有公共部分 连通块的定义是块内的任意两个点 u v 都必定存在路径 e u

  • luogu P2078 朋友

    题目背景 小明在A公司工作 xff0c 小红在B公司工作 题目描述 这两个公司的员工有一个特点 xff1a 一个公司的员工都是同性 A公司有N名员工 xff0c 其中有P对朋友关系 B公司有M名员工 xff0c 其中有Q对朋友关系 朋友的朋

  • luogu P1593 因子和

    不要吐槽博主总做这些数论氵题 首先我们看到这种因数问题 果断质因数分解 所以当前数 a 61 p 1 k 1 p 2 k 2 p m k m 可得 a b 61 p 1 k 1 b p 2 k 2 b p m k m b 考虑因数和 假设数

  • 洛谷 P2651 添加括号III

    思路 xff1a a1肯定是分子 xff0c a2肯定是分母 xff0c 只要确认a1a3a4 a2是否是整数 只要确认a1a3a4 a2是否是整数 每次将a2 61 a2 gcd a2 ai i 61 1 3 4 5 即可约分 span

  • P2651 添加括号III（数论，洛谷，java，最大公约数）

    洛谷链接 xff1a https www luogu org problem P2651 span class token keyword import span java span class token punctuation span

  • Luogu 3632 [APIO 2011] 寻路

    传送门正解参考代码 传送门 正解 暴力连边跑最短路就好了 xff0c 只不过代码太长太难写啦 xff01 参考代码 span class hljs preprocessor include lt cstdio gt span span cl

  • Luogu 3634 [APIO 2012] 守卫

    传送门思路正解参考代码 传送门 思路 感觉自己越来越笨了 首先 xff0c 很明显这道题需要把没有看到忍者的区间给删去 xff0c 可以用前缀和 O n O n 处理 xff0c 然后对没有删去的地方重新标号 重新标号时 xff0c 需要对

  • Luogu 1552 [APIO 2012] 派遣

    传送门思路参考代码 传送门 思路 唉 xff0c 我太弱了 xff0c 什么都不会 xff0c 题读错了两次 xff0c 一开始读成了一个一般的背包 xff0c 然后读成了一个价值和花费相同的背包 xff0c 最后才发现原来是一个价值为 1

  • Luogu 3647 [APIO 2014] 连珠线

    传送门思路参考代码 传送门 思路 唉 xff0c 我太弱了 xff0c 又看错题了 题目中说一个新的珠子和一个已经添加的珠子连接起来 xff0c 我没有看到 xff0c 然后就凉了 立个 flag xff1a 已经连续看错五题了 xff0c

  • Luogu 3645 [APIO 2015] 雅加达的摩天楼

    传送门思路正解参考代码Update 传送门 思路 唉 xff0c 我太弱了 xff0c 我都看出来要分块了 xff0c 就是做不来 不过终于把题读对了 先来看子任务三怎么做 显然可以有一个 O m 2 O m 2

  • Luogu 3778 [APIO 2017] 商旅

    传送门思路参考代码 传送门 思路 唉 xff0c 我太弱了 xff0c 什么都不会 看到这道题就想到了二分答案找负环 xff0c 但是怎么做呢 xff1f 完全不会 唉 xff0c 我太弱啦 xff01 先注意题目中说可以重复经过点和边 x

  • Luogu 2146 [NOI 2015] 软件包管理器

    传送门思路参考代码 传送门 思路 唉 xff0c 我太弱了 xff0c 什么都不会 xff0c 好不容易遇到一道傻逼题 xff0c 又出了个傻逼错误 xff0c 爆得只剩 30 30 分了 唉 xff0c 我太弱啦 xff01 显然 xff

  • Luogu 1117 [NOI 2016] 优秀的拆分

    传送门思路利用后缀数组解决重复子串问题注意事项参考代码 传送门 思路 唉 xff0c 我太弱了 xff0c 什么都不会 xff0c 连暴力都想不到 xff0c 唉 xff0c 我太弱啦 xff01 考虑暴力法 xff0c 可以枚举一个中间点

  • Luogu 1712 [NOI 2016] 区间

    传送门思路参考代码 传送门 思路 唉 xff0c 我太弱了 xff0c 什么都不会 xff0c 这么个傻逼题 xff0c 居然把离散化写错了 xff0c 唉 xff0c 我太弱啦 xff01 显然我们可以考虑枚举最短长度和最长长度 xff0

  • Luogu 2114 [NOI 2014] 起床困难综合症

    传送门思路参考代码 传送门 思路 按位贪心 但是我太弱了 xff0c 明明可以 O n O n 预处理 xff0c 我却只会 O 32 n O

  • Luogu 2354 [NOI 2014] 随机数生成器

    传送门思路参考代码 传送门 思路 唉 xff0c 我太弱了 xff0c 什么都不会 xff0c 这么一个傻逼题 xff0c 我却看成了要你构造一种交换方案使得答案最小 xff0c 结果后面的额外交换是题目给定的 唉 xff0c 我太弱啦 x

  • Luogu 2305 [NOI 2014] 购票

    传送门思路别人家的题解弱化的传送门 xff08 Luogu 3994 高速公路 xff09 参考代码 对于没有距离限制的 50 分 参考代码 对于 100 分的数据参考代码Remarks 传送门 思路 唉 xff0c 我太弱了 xff0c

  • 洛谷 - p2651 添加括号III(思维，数学)

    题目传送 题意 思路 我们首先想想如何判断一个分数是否能约分成整数 判断方法 1 我们可以分解分子的质因子和分母的质因子 xff0c 如果分母的质因子数量和种类数完全被分子的质因子包括 xff0c 那么一定可以约分成为整数 2 如果分母的所

  • P1586 四方定理

    Powered by NEFU AB IN Link 文章目录 P1586 四方定理 题意 思路 代码 P1586 四方定理 题意 四方定理是众所周知的 任意一个正整数n 可以分解为不超过四个整数的平方和 给定的正整数n 编程统计它能分解的

随机推荐

  • 服务器内存显示不正常,服务器内存显示不正常

    服务器内存显示不正常 内容精选 换一换 Linux操作系统XEN实例变更为KVM实例前 xff0c 必须完成驱动的安装和配置 本节操作指导您手动安装Linux云服务器驱动 配置磁盘自动挂载等 xff0c 并将XEN实例变更为KVM实例 如需

  • 调试 JavaScript 脚本

    随着 JavaScript 应用的复杂性逐渐提高 xff0c 开发者需要有力的调试工具来帮助他们快速发现问题的原因 xff0c 并且能高效地修复它 Chrome DevTools 提供了一系列实用的工具使得调试 JavaScript 应用不

  • luogu P1593 因子和

    不要吐槽博主总做这些数论氵题 首先我们看到这种因数问题 果断质因数分解 所以当前数 a 61 p 1 k 1 p 2 k 2 p m k m 可得 a b 61 p 1 k 1 b p 2 k 2 b p m k m b 考虑因数和 假设数

  • centos7安装完显示设备报错_centos7安装Xrdp报错连接5910端口错误

    centos7安装Xrdp报错连接5910端口错误 环境centos7 4 xff0c Xrdp 0 9版本 我们在用yum安装完成Xrdp后进行远程登陆时候输入用户密码后 xff0c 登陆报错如图形式 通过图中信息我们可以判断密码验证是通

  • 【C语言中“%d %%d %%%d“代表的意思】

    C语言中 d d d 34 代表的意思 1 d 表示按整型输出后面给出的变量的值 输出整型 2 d 在C语言中就是输出一个 xff0c 而d为一个普通字符 xff0c 则 d输出 d 3 d 三个 xff0c 前面两个 输出一个 xff0c

  • #C++初学记录（算法4）

    A Serval and Bus It is raining heavily But this is the first day for Serval who just became 3 years old to go to the kin

  • 8x8点阵字模生成器_玩转单片机 16X16点阵

    来说一下16X16点阵的编写技巧 xff0c 主要讲一下思路 xff0c 因为在写16X16点阵驱动时 xff0c 很多人一上来大脑一片空白啊 xff0c 根本无从下手 xff0c 我这里举一个例子讲下思路 xff0c 以后大家可以按照我下

  • SQL Server将列以分隔符分割后存到临时表

    begin if object id 39 tempdb t 39 is not null drop table t create table t filepath nvarchar 300 declare 64 filePathStr n

  • linux关闭xserver命令,图形界面 X Server 的关闭与启动

    Linux图形界面多数使用的是 X Server 我们有时需要关闭 重启它 比如 安装 NVIDIA 的驱动程序时 xff0c 就需要先关闭 X server 希望让系统以 server 方式运行 关闭桌面环境以降低不必要的性能损耗 Ubu

  • kali Linux下为Apache2配置SSL证书

    SSL证书是在阿里云免费申请的 xff0c 下载的Apache版本 里面有三个文件 xff0c 一个a key xff0c 一个a public crt和a chain crt 其中官方文档中配置是基于apache的httpd conf x

  • [读书笔记] 树莓派 raspberry pi cluster的搭建实践

    地址在这里 http raspberrywebserver com raspberrypicluster adding more nodes to the cluster html 或者是在这里 xff1a http raspberrywe

  • 解决Codeforces访问慢的本地方案

    参考 xff1a http m blog csdn net blog Xiangamp 42245923 转载于 https www cnblogs com acvc p 4249846 html

  • c 语言信号量,C语言中的信号量

    信号量是学习同步的一个好方式 xff0c 但是它们实际上并没有像互斥体和条件变量一样被广泛使用 尽管如此 xff0c 还是有一些同步问题可以用信号量简单解决 xff0c 产生显然更加合适的解决方案 这一章展示了C语言用于处理信号量的API

  • linux 密码少于4的位数,详解Linux Shell 实现一个获取任意位数的随机密码的脚本_linux shell_脚本之家...

    Shell 命令行 xff0c 实现一个获取任意位数的随机密码的脚本 每次我们想要获得一个密码的时候都很头疼 xff0c 于是我之前自己用nodejs写了一个 Shell 脚本 这两天在学习 bash Shell 所以 xff0c 想用同样

  • Go 语言中格式化时间

    一个 demo 上个 demo 看一下 xff0c 这段代码会输出当前时间 xff0c 类似 2017 09 20 22 05 58 xff1a span class hljs keyword package span main span

  • 【安装Python环境】之“安装 setuptools ”时出现的问题以及解决办法

    安装Python环境时 xff0c 还需要安装 setuptools 与 pip xff0c 但是安装setuptools时出现了几个问题 xff0c 如下 xff1a setuptools 与 pip 下载地址如下 xff1a https

  • Ubuntu网络频繁掉线解决方案

    年底了 xff0c 实验室终于给配了个电脑 xff08 Ubuntu系统 xff09 xff0c 博主欣喜若狂啊 xff0c 然而装好后发现无线网频繁掉线 xff0c 重启网络后能正常上网2 3分钟然后又掉线 xff0c 再重启又能上网2

  • 【Linux基础】查看某一端口是否开放(1025为例)

    1 使用lsof 命令来查看端口是否开放 lsof i 1025 如果有显示说明已经开放了 xff0c 如果没有显示说明没有开放 lsof list open files 是一个列出当前系统打开文件的工具 在linux环境下 xff0c 任

  • Sublime Text 3下C/C++开发环境搭建

    Sublime Text 3下C C 43 43 开发环境搭建 之前在Linux Mint 17一周使用体验中简单介绍过Sublime Text 1 Sublime Text 3安装 Ubuntu Linux Mint的软件管理器中已经能够

  • luogu p2651 添加括号Ⅲ

    题目描述 现在给出一个表达式 xff0c 形如a1 a2 a3 an 如果直接计算 xff0c 就是一个个除过去 xff0c 比如1 2 1 4 61 1 8 然而小A看到一个分数感觉很不舒服 xff0c 希望通过添加一些括号使其变成一个整

热门标签