SGU 126. Boxes

2023-11-21 09:20
文章标签 126 boxes sgu

本文主要是介绍SGU 126. Boxes,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题面Codeforces. Programming competitions and contests, programming communityhttps://codeforces.com/problemsets/acmsguru/problem/99999/126大意:给出A,B(0<A+B<2^31),每次操作可以将其中一个数减去另一个数,并让另一个数乘2,即(A,B)->(2A,B-A),前提是B>=A

问最终使得A,B有一个为0的最少操作数,或判定无解

由于2A,B-A这个形式非常像辗转相减法中(A,B)->(A,B-A),只是A变成2A了,于是我们考虑一次操作后这个2A对gcd的影响,由于gcd(A,B)=gcd(A,B-A),所以gcd(2A,B-A)只能是gcd(A,B)或 2gcd(A,B)并且我们知道最终态为(A+B,0),gcd为A+B

于是可以判断有解的充要条件为:A+B=2^kgcd(A,,B) k为自然数

那么,判断有解后如何求出操作数呢?其实,操作数就为k,下面我们来证明这一点

首先,设d=gcd(A, B),则A=xd,B=yd,其中gcd(x, y)=1(为了方便,我们令x<=y)

代入A+B=2^kgcd(A,,B),得到xd+yd=2^k d,即x+y=2^k

若k=0,则x,y中一个为0,一个为1,即A,B中有一个为0,显然操作数为k=0

若k>0,则2^k为偶数,x,y奇偶性相同,可以证明x和y都是奇数(若都是偶数则不互质)

操作后变为(2xd,(y-x)d),其中2x,y-x都为偶数,则gcd必然变为原来的两倍,即2d

由A+B=2^k d可知,k次操作后即到达目标态,得证

具体实现非常简单

这篇关于SGU 126. Boxes的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/401398

相关文章

【SGU】180. Inversions(归并排序求逆序数)

以前一般用树状数组和线段树做这种题 这次换个思路试试,归并排序! #include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const int maxn = 111111;int n;int array[maxn];int tmp[maxn];L

【SGU】271. Book Pile(双端队列模拟)

一摞书,2个操作,一个操作是在书堆上加一本,第二个将前K个书翻转 看别人用Splay树做的,但是可以用双端队列模拟,因为K个书之后的书位置已经定下来了,所以只需要记录在队列头加书还是尾加书 #include<cstdio>#include<string>#include<algorithm>#include<queue>#include<stack>#include<cstrin

【SGU】115. Calendar 水题= =

传送门:【SGU】115. Calendar 题目分析:2001年1月1号星期1,然后就没什么好说的了= = 代码如下: #include <map>#include <vector>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespac

【SGU】 114. Telecasting station 中位数

传送门:【SGU】 114. Telecasting station 题目分析:一个位置多个城市可以看成多个城市在同一位置,然后就可以求中位数了,易知最优的位置一定在中位数上。 代码如下 : #include <map>#include <vector>#include <cstdio>#include <cstring>#include <iostream>

【SGU】113. Nearly prime numbers 合数分解

传送门:【SGU】113. Nearly prime numbers 题目分析:O(sqrt(N))。。 代码如下: #include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std ;#define rep( i , a , b ) for

环境配置 --- miniconda安装torch报错OSError: [WinError 126] 找不到指定的模块

环境配置 — miniconda安装torch报错OSError: [WinError 126] 找不到指定的模块。 CSDN 原因:fbegmm.dll文件出现问题 解决方案: 使用依赖分析工具https://github.com/lucasg/Dependencies/releases/tag/v1.11.1 检测报错提示的那个dll文件发现哪个文件报错就下载一个新的然后放到torch/

python interpreter process exited with a non-zero exit code 126 权限不够

分析 文件可能没有设置为可执行状态。 解决 通过以下命令检查和修改文件权限 ls -l /path/to/python 如果文件的权限没有设置为可执行(即没有x权限),可以使用 chmod 命令来添加执行权限 chmod +x /path/to/python

数学建模学习(126):基于Python的最优最劣法(BWM)在多标准决策中的应用

文章目录 1. 引言2. 案例2.1 最优最劣法(BWM)的原理2.2 数据来源和定义2.3 Python实现2.4 结果分析 3. 结论参考文献 1. 引言 在现代决策分析中,如何合理地评估和选择多个备选方案是一项复杂的任务。多标准决策分析(MCDA)方法提供了一种科学的途径,通过对多个标准的综合评估,帮助决策者做出最优选择。本文将介绍一种重要的MCDA方法——最优最劣法(B

【基于Python的Selenium2自动化测试】05 - 模拟126邮箱的发邮件功能

直接上代码,如下: # coding=utf-8from selenium import webdriverimport timedriver = webdriver.Firefox()driver.get("http://www.126.com")time.sleep(1) # 加一个延时操作,才能定位到下面的iframeiframe1 = driver.find_element_b