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

题解 | #G.Gcd# 2023牛客暑期多校6

G.Gcd

数论

题目大意

给定一个包含两个非负数的初始集合 S = { x , y } S=\{x,y\} S={x,y}
每次操作可以选定其中不相等的两个数 a , b a,b a,b ,并将 a − b a-b ab g c d ( a , b ) gcd(a,b) gcd(a,b) 置入集合 S S S ,其中 g c d ( 0 , a ) = a gcd(0,a)=a gcd(0,a)=a
可以操作任意次,问能否使得集合 S S S 包含非负数 z z z

前置知识点

裴蜀定理

解题思路

根据裴蜀定理,两个正整数辗转相减只能得到他们最大公约数的倍数//
因此对于 z z z ,判断其是否是 g c d ( x , y ) gcd(x,y) gcd(x,y) 的倍数即可

如果 z z z g g g 的倍数,则可以通过以下操作得到 z z z

  1. g = g c d ( x , y ) g=gcd(x,y) g=gcd(x,y) 置入集合
  2. x x x 作为 g g g 的倍数,其加减任意次 g g g 便可得到任意 g g g 的倍数。
    只能减不能加怎么办呢//先把 x x x 减到 − g -g g 就好了

值得注意的是,本题的数据约束为非负数,这意味着需要对 0 0 0 的情况进行特判//

  1. 对于 z = 0 z=0 z=0 ,仅当 x , y x,y x,y 0 0 0 时有解
  2. 对于 x = 0 x=0 x=0 y = 0 y=0 y=0 ,仅当 z z z 与其中之一相等时有解(实际上这条也满足裴蜀定理//只是懒得重写 g c d gcd gcd 了)

参考代码

参考代码为已AC代码主干,其中部分功能需读者自行实现

void solve()
{ll x,y,z;cin >> x >> y >> z;if(x&&y&&z==0) {cout << NO;return;}if((x==0)||(y==0)) if(z==x||z==y) {cout << YES;return;} else {cout << NO;return;}ll g=gcd(x,y);if(z%g) cout << NO;else cout << YES;
}

相关文章:

题解 | #G.Gcd# 2023牛客暑期多校6

G.Gcd 数论 题目大意 给定一个包含两个非负数的初始集合 S { x , y } S\{x,y\} S{x,y} 每次操作可以选定其中不相等的两个数 a , b a,b a,b &#xff0c;并将 a − b a-b a−b 或 g c d ( a , b ) gcd(a,b) gcd(a,b) 置入集合 S S S &#xff0c;其中 g c d ( 0 , a …...

苍穹外卖day10——订单状态定时处理(Spring Task)、来单提醒和客户催单(WebSocket)

预期效果 对于超时没处理的需要定时程序处理。基于SpringTask实现。 来单提醒和客户催单。基于WebSocket实现。 Spring Task 介绍 Cron表达式 周几通常不能和日一起指定。 cron表达式在线生成器 在线Cron表达式生成器 入门案例 创建定时任务类 /*** 定义定时任务类*/ Slf4j…...

【多线程初阶】多线程案例之单例模式

文章目录 前言1. 什么是单例模式2. 饿汉模式3. 懒汉模式 --- 单线程版4. 懒汉模式 --- 多线程版5. 懒汉模式 --- 多线程改进版总结 前言 本文主要给大家讲解多线程的一个重要案例 — 单例模式. 关注收藏, 开始学习吧&#x1f9d0; 1. 什么是单例模式 单例模式是一种很经典的…...

跨境选品怎么选?建议独立站卖家收下这份利基产品查找攻略!

跨境电商平台现在可谓是火热发展中&#xff0c;独立站出海风口&#xff0c;其实选择的机会还真不少&#xff0c;相比国内电商的发展势头&#xff0c;看得出来&#xff0c;未来跨境电商的大门&#xff0c;对你而言&#xff0c;敞开着。选品这事儿&#xff0c;就像你上战场前挑选…...

[C++项目] Boost文档 站内搜索引擎(1): 项目背景介绍、相关技术栈、相关概念介绍...

项目背景 Boost库是C中一个非常重要的开源库. 它实现了许多C标准库中没有涉及的特性和功能, 一度成为了C标准库的拓展库. C新标准的内容, 很大一部分脱胎于Boost库中. Boost库的高质量代码 以及 提供了更多实用方便的C组件, 使得Boost库在C开发中会被高频使用 为方便开发者学…...

opencv-32 图像平滑处理-高斯滤波cv2.GaussianBlur()

在进行均值滤波和方框滤波时&#xff0c;其邻域内每个像素的权重是相等的。在高斯滤波中&#xff0c;会将中心点的权重值加大&#xff0c;远离中心点的权重值减小&#xff0c;在此基础上计算邻域内各个像素值不同权重 的和。 基本原理 在高斯滤波中&#xff0c;卷积核中的值不…...

Windows 环境Kubernetes安装

目录 前言 安装 Docker 安装 Kubernetes Windows 安装 kubectl 介绍 安装 开启 Kubernetes 前言 Docker作为当前最流行的容器化平台&#xff0c;为Kubernetes提供了强大的容器化技术基础。Kubernetes与Docker的结合&#xff0c;使得容器化应用程序在大规模集群中得以简…...

自建类ChatGPT服务:本地化部署与远程访问教程

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…...

常用SQL语句总结

SQL语句 文章目录 SQL语句1 SQL语句简介2 DQL&#xff08;数据查询语句&#xff09;3 DML&#xff08;数据操纵语句&#xff09;4 DDL&#xff08;数据定义语句&#xff09;5 DCL&#xff08;数据控制语句&#xff09;6 TCL&#xff08;事务控制语句&#xff09; 1 SQL语句简介…...

arm交叉编译lmbench

一、下载lmbench www.bitmover.com/lmbench 官网下载&#xff0c;http://www.bitmover.com/lmbench/lmbench3.tar.gz 我没有下载下来&#xff0c;找的别人的百度云下载 链接: https://pan.baidu.com/s/1tGo1clCqY-jQPN8G1eWSsg 提取码: f6jd 二、修改makefile 修改三个文件…...

ExtJs 7.7.0 下载方法与去除trial水印

背景 最近发现Sencha ExtJs发布了ExtJs7.7.0版本&#xff0c;立刻下载了SDK包&#xff0c;许多朋友不知如何下载&#xff0c;如何去除右上角的trial水印。本文讲下相关下载技巧与方法。 下载SDK 首先需要申请试用&#xff0c;申请地址如下&#xff0c;需要注意可能需要梯子&…...

Android11开发规划

文章目录 规划总结规划 提示:这里可以添加本文要记录的大概内容: 从本文开始,会介绍如何移植瑞芯微提供的Android11源码到自己的RK3568的板子上 下面是整个Android开发的规划: 包括以下部分: … 一、移植部分 下载编译瑞芯微提供的源码 瑞芯微原厂源码目录介绍...

活动隔断在现在酒店运用的方式

活动隔断是一种在酒店内部划分空间的方式&#xff0c;用于实现不同活动的隔离和隐私。现代酒店常用的活动隔断方式有以下几种&#xff1a; 1. 固定隔断&#xff1a;使用墙体、固定屏风或者板材等材料&#xff0c;将空间划分为不同的房间或区域。这种方式常用于划分客房、会议室…...

Jenkins工具系列 —— 插件 钉钉发送消息

文章目录 安装插件 Ding TalkJenkins 配置钉钉机器人钉钉APP配置项目中启动钉钉通知功能 安装插件 Ding Talk 点击 左侧的 Manage Jenkins —> Plugins ——> 左侧的 Available plugins Jenkins 配置钉钉机器人 点击 左侧的 Manage Jenkins &#xff0c;拉到最后 钉…...

LeetCode 26 题:删除有序数组的重复项

思路 在写这一个题时&#xff0c;我突然想到了Python中的 set&#xff08;&#xff09;函数可能会有大用处&#xff0c;便选择了用Python写。 set&#xff08;&#xff09;函数可以将列表转化为集合&#xff0c;集合会保证元素的单一性&#xff0c;所以会自动删去相同字符。 …...

优雅地切换node版本(windows)

文章目录 1、下载并安装nvm2、nvm的使用3、处理npm版本与nodejs版本不匹配问题&#xff08;通常不会有这个问题&#xff09; 1、下载并安装nvm 卸载已安装的node&#xff1a;控制面板-程序-找到node并卸载 通常在控制面板中卸载后&#xff0c;nodejs目录、环境变量、注册表就自…...

反诈:吴明军、黄亮领导的WIN生活资金盘,大家警惕防范此类诈骗

消息已经证实&#xff01;“米粒”无法变现&#xff0c;数以万计的会员深套“315万民商城”&#xff0c;维权艰难&#xff0c;血汗钱无法讨回。 其实这一点笔者并不感到太意外&#xff0c;因为万民商城资金传销盘的定性之前就已经发文揭露过&#xff0c;并反复提醒大家小心警惕…...

shell、bash的关系及bash的特性(一)

一、概念 shell是壳&#xff0c;是运行在终端中的文本互动程序。Shell相当于是一个翻译&#xff0c;把我们在计算机上的操作命令&#xff0c;翻译为计算机可识别的二进制命令&#xff0c;传递给内核&#xff0c;以便调用计算机硬件执行相关的操作&#xff1b;同时&#xff0c;计…...

【问题随记】

ubuntu 14.04源更新(sources.list) deb http://mirrors.aliyun.com/ubuntu/ trusty main restricted universe multiverse deb http://mirrors.aliyun.com/ubuntu/ trusty-security main restricted universe multiverse deb http://mirrors.aliyun.com/ubuntu/ trusty-update…...

Stable Diffusion AI绘画学习指南【常用模型,采样器介绍】

常用采样器、目前有20个采样步骤越多每个步之间的降噪越小&#xff0c;减少采样过程中的截断误差&#xff0c;结果越好 学微分方程求解器 Euler&#xff08;最简单的采样器&#xff0c;采样过程中不加随机噪声&#xff0c;根据采样计划来执行每个步骤中的噪声&#xff0c;并使…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...