【二进制求公约数】【数学】【数论】2543. 判断一个点是否可以到达

本文涉及知识点

二进制求公约数

LeetCode2543. 判断一个点是否可以到达

给你一个无穷大的网格图。一开始你在 (1, 1) ,你需要通过有限步移动到达点 (targetX, targetY) 。
每一步 ,你可以从点 (x, y) 移动到以下点之一:
(x, y - x)
(x - y, y)
(2 * x, y)
(x, 2 * y)
给你两个整数 targetX 和 targetY ,分别表示你最后需要到达点的 X 和 Y 坐标。如果你可以从 (1, 1) 出发到达这个点,请你返回true ,否则返回 false 。
示例 1:
输入:targetX = 6, targetY = 9
输出:false
解释:没法从 (1,1) 出发到达 (6,9) ,所以返回 false 。
示例 2:
输入:targetX = 4, targetY = 7
输出:true
解释:你可以按照以下路径到达:(1,1) -> (1,2) -> (1,4) -> (1,8) -> (1,7) -> (2,7) -> (4,7) 。
提示:
1 <= targetX, targetY <= 109

预备知识

辗转相除法(欧几里得)求最大公约数

( a , b ) → 不失一般性,令 a > = b ( c = a m o d    b , d = b ) → 不失一般性,令 c > = d ( e = c m o d    d , f = d ) ⋯ (a,b)^{不失一般性,令a >= b}_\rightarrow (c= a \mod b,d= b) ^{不失一般性,令c >= d}_\rightarrow (e=c \mod d,f=d) \cdots (a,b)不失一般性,令a>=b(c=amodb,d=b)不失一般性,令c>=d(e=cmodd,f=d)
直到最后的两个数一个为0,则公约数是另外一个。比如:e为0,最大公约数就是f。f为0,最大公约数为e。
a,b不断变小,有限次数一定有一个数变为0。
令某两个数的最大公约数为q, 则这两个数可以表示为 q × a , q × b 则 q × ( a m o d    b ) , q × b 的最大公约数为 q 则这两个数可以表示为q \times a,q \times b 则 q \times (a \mod b) , q \times b 的最大公约数为q 则这两个数可以表示为q×a,q×bq×(amodb),q×b的最大公约数为q
a%b 为0,也符合数学定义: 0和任何数x的最大公约数是x。

二进制求公约数

求a,b的最大公约数。
一,如果a,b都是偶数,则GCD(a,b) = 2*GCD(a,b)。
二,如果a 是偶数,b是奇数(反之类似)。GCD(a,b)=GCD(a/2,b)。b是奇数,所以他们的公约数不包括2。
三,两者都是奇数。
3.1,两者相等。a就是最大公约数。
3.2,a b不等,不失一般性,令a>b。GCD(a,b) == GCD(a+b,b) == GCD((a+b)/2,b)
由于a,b是不断变小,一定会相等。

数学

本题    ⟺    \iff (targetX, targetY)能否变成(1,1)。
如果 argetX, targetY 最大公约是g × \times × 2m ,按二进制求最大公约数的做法,最终变成(g,g)。如果g=1,则一定能到达。
下面来证明 g ≠ \neq = 1 ,则一定不能到达。
4种操作对公约数的影响只有两种:
一,最大公约数不变。
二,最大公约数除以2。
这4个操作若干次后,两个数的最大公约是:g × \times × 2m1 ,m1 ∈ \in [0,m]。
因为:g ≠ \neq = 1 ,故: g × \times × 2m1 ≠ \neq = 1 。

娱乐型求最大公约数

这种求公约数的方式不好理解,不要在工程中使用。

int GCD(int x, int y)
{
	if ((x && y))
	{
		while ((x %= y) && (y %= x));
	}
	return x + y;
}
class Solution {
public:
	bool isReachable(int targetX, int targetY) {
		const int g = GCD(targetX, targetY);
		return 0 == (g & (g - 1));
	}
};

二进制求公约数

int GCD(int x, int y)
{	
	int ret = 1;
	while (x != y)
	{
		if (x < y)
		{
			swap(x, y);
		}
		const bool odd1 = x & 1;
		const bool odd2 = y & 1;
		if (odd1 & odd2)
		{
			x = (x + y) / 2;
		}
		else if (odd1)
		{
			y /= 2;
		}
		else if (odd2)
		{
			x /= 2;
		}
		else
		{
			ret *= 2;
			x /= 2;
			y /= 2;
		}
	}
	return x * ret;
}
class Solution {
public:
	bool isReachable(int targetX, int targetY) {
		const int g = GCD(targetX, targetY);
		return 0 == (g & (g - 1));
	}
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/479021.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于python+vue灾害应急救援平台flask-django-php-nodejs

灾害应急救援平台的目的是让使用者可以更方便的将人、设备和场景更立体的连接在一起。能让用户以更科幻的方式使用产品&#xff0c;体验高科技时代带给人们的方便&#xff0c;同时也能让用户体会到与以往常规产品不同的体验风格。 与安卓&#xff0c;iOS相比较起来&#xff0c;…

(二)RabbitMQ实战——rabbitmq高可用集群搭建

前言 本节内容是关于rabbitmq高可用集群的部署搭建&#xff0c;使用的是centos7系统&#xff0c;我们准备三台服务器作为rabbitmq的高可用服务器&#xff0c;rabbitmq集群本身不是天然支持高可用的&#xff0c;我们通过配置rabbitmq服务器的镜像队列&#xff0c;以确保消息可以…

突然发现!原来微信批量自动加好友这么简单!

你知道如何更好地管理和利用微信资源&#xff0c;实现客户拓展和沟通吗&#xff1f;下面就教大家一招&#xff0c;帮助大家实现统一管理多个微信号以及批量自动加好友。 想要统一管理多个微信号&#xff0c;不妨试试微信管理系统&#xff0c;不仅可以多个微信号同时登录&#…

无插件网页视频播放器,支持图像绘制(包含方格子、方框等),支持音视频播放、支持录像截图,提供源码下载

前言 本播放器内部采用jessibuca插件接口&#xff0c;支持录像、截图、音视频播放等功能。播放器播放基于ws流&#xff0c;图像绘制操作&#xff1a;1&#xff09;支持绘制方格子&#xff0c;用于监控移动检测画框&#xff1b;2&#xff09;支持绘制不透明方框&#xff0c;用于…

如何进行设备的非对称性能测试

非对称性能测试介绍 RFC2544是RFC组织提出的用于评测网络互联设备&#xff08;防火墙、IDS、Switch等&#xff09;的国际标准。主要是对RFC1242中定义的性能评测参数的具体测试方法、结果的提交形式作了较详细的规定。标准中定义了4个重要的参数&#xff1a;吞吐量&#xff08…

【No.12】蓝桥杯可撤销并查集|查找|合并|撤销(C++)

前置知识 蓝桥杯并查集|路径压缩|合并优化|按秩合并|合根植物(C)-CSDN博客 可撤销并查集 关键注意 可撤销并查集的撤销功能如何实现可撤销并查集能不能用路径压缩 可撤销并查集(Reversible Union-Find)是一种扩展了标准并查集(Union-Find)数据结构的数据结构&#xff0c;它允…

Python螺旋折线蓝桥杯(来源lanqiao.cn 题目176) 时间超限

题目描述 如图所示的螺旋折线经过平面上所有整点恰好一次。 对于整点(X, Y)&#xff0c;我们定义它到原点的距离dis(X, Y)是从原点到(X, Y)的螺旋折线段的长度。 例如dis(0, 1)3, dis(-2, -1)9 给出整点坐标(X, Y)&#xff0c;你能计算出dis(X, Y)吗&#xff1f; 输入格式 …

【Unity】层(Layer)详解

1.什么是Layer? 我们在做游戏开发的时候&#xff0c;尤其是场景比较复杂的时候&#xff0c;我们就需要使用Layer来分类。 比如&#xff1a; 排除不被灯光照亮的Layer 射线检测特定的 Layer 摄像机只能看到某些 Layer 对象之间的碰撞检测 Layer … 2.添加Layer ①在Inspecto…

GZ083 产品艺术设计赛题第十

全国职业院校技能大赛 产品艺术设计赛项赛题十 赛项名称 产品艺术设计 英语名称 Product Art Design 赛项编号 GZ083 归属产业 数字产业 任务名称 “绣羽鸣春”鸟形象主题文具收纳袋设计 赛项组别 中职组 高职组 □学生组 □教师组 □师生联队试点赛项 R学生组 …

Echarts地图之——如何给地图添加背景图片

上期我们已经给地图添加了一个阴影3d的效果&#xff0c;但是背景纯色的感觉还是不怎么好看&#xff0c;希望能给地图加个背景图。 一般来说给地图加背景图的情况较少&#xff0c;加个渐变色或者根据数据的情况给某些省份设置不一样的背景色&#xff0c;这样的做法是比较多的。…

C++关键字:const

文章目录 一、const的四大作用1.修饰 变量、数组2.修饰 函数的形参、修饰 引用 (最常用&#xff09;3.修饰 指针&#xff1a;常量指针、指针常量 、只读指针4.修饰 类的成员函数、修饰 类的对象 一、const的四大作用 1.修饰 变量、数组 1.const修饰变量&#xff1a; 被const修…

MySQL 如何修改密码

** MySQL 如何修改 root 密码 ** 一、如果 mysql 未设置 root 初始密码&#xff0c;可直接登录&#xff0c;修改密码。 mysql -u root -p --- 连接权限数据库 mysql> use mysql; --- 低版本 mysql 5.x mysql> update user set passwordpassword(123) where userro…

Type-C一拖多智能快充线方案

一拖二快充线PD芯片&#xff1a;技术革新与充电效率的提升 在移动设备日益普及的今天&#xff0c;充电技术的革新显得尤为重要。一拖二快充线PD芯片作为充电技术领域的一项创新成果&#xff0c;不仅提高了充电效率&#xff0c;还满足了用户多设备同时充电的需求。本文将深入探…

Python 三维可视化库之visualpython使用详解

概要 在科学计算和数据可视化领域,交互式三维可视化是一种强大的工具,可以帮助研究人员直观地探索数据和模拟结果。Python 的 visualpython 库就是这样一款强大的工具,它提供了丰富的功能和易用的接口,可以让用户轻松创建交互式的三维场景,展示复杂的科学计算结果。本文将…

springboot项目yml文件中${}的使用

作用 项目启动时可以灵活的通过修改环境变量来替换配置中的值&#xff0c;如果没有传该环境变量时&#xff0c;就是用默认值&#xff1b; 格式&#xff1a;${自定义参数名:默认值} 代码举例&#xff0c;已开启应用的端口号为例&#xff1a; server: port: ${SERVER_PORT:9…

Python代码实现Excel表格转HTML文件

Excel工作簿是常用的表格格式&#xff0c;广泛用于组织、分析及展示数据。Excel文件通常需要专门的文档阅览器进行查看。如果我们想要以更兼容的方式展示Excel表格&#xff0c;可以将其转换为HTML格式&#xff0c;使其能够在各种浏览器中直接进行查看。同时&#xff0c;将Excel…

[VulnHub靶机渗透] Kioptrix1.2

&#x1f36c; 博主介绍&#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 hacker-routing &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【应急响应】 【Java、PHP】 【VulnHub靶场复现】【面试分析】 &#x1f389;点赞➕评论➕收…

腾讯在GDC 2024展示GiiNEX AI游戏引擎现已投入《元梦之星》中开发使用,展示强大AIGC能力

在近日举行的GDC 2024游戏开发者大会上&#xff0c;腾讯揭开了其AI Lab团队精心打造的GiiNEX AI游戏引擎的神秘面纱。这款引擎依托先进的生成式AI和决策AI技术&#xff0c;为游戏行业带来了革命性的变革。 相关阅读&#xff1a;腾讯游戏出品&#xff01;腾讯研效AIGC&#xff…

今天聊聊Docker

在数字化时代&#xff0c;软件应用的开发和部署变得越来越复杂。环境配置、依赖管理、版本控制等问题给开发者带来了不小的挑战。而Docker作为一种容器化技术&#xff0c;正以其独特的优势成为解决这些问题的利器。本文将介绍Docker的基本概念、优势以及应用场景&#xff0c;帮…

惠普EliteBook使用VirtualBox安装ISO镜像

实验环境 虚拟机软件&#xff1a;Oracle VM VirtualBox 6.1.16镜像文件&#xff1a;CentOS-7-x86_64-Minimal-2009.iso笔记本&#xff1a;惠普EditBook操作系统&#xff1a;Window10 BIOS开启虚拟化技术 一遍笔记本都不会开启虚拟化技术的&#xff0c;但是在window里使用虚拟…