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

B - GCD Subtraction

文章目录

  • AtCoder Regular Contest 159
    • B - GCD Subtraction

AtCoder Regular Contest 159

B - GCD Subtraction

  1. 问题:每次A,B都减去gcd(A,B),求其中一个减到0至少需要多少次
  2. 主要思路:
    1. 首先第一步应该想到每次减去的数,先减去的数一定是后减去的数的因子,可以直接将A/gcd(A,B),B/gcd(A,B),计算两个互质数的答案
    2. gcd(A,B)=1,考虑什么时候不再减去1,假设为d,那么有 d|(A-t),d|(B-t),于是有 A = i ∗ d + t A = i*d+t A=id+t, B = j ∗ d + t B = j*d+t B=jd+t 1 ≤ t < d 1\le t <d 1t<d, d有以下性质
      d 是质数且 d ∣ ( A − B ) d 是质数 且 d| (A-B) d是质数且d(AB)
    3. 每次求 A − B A-B AB的所有质因子
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b){return b ==0?a:gcd(b,a%b);
} 
void get(LL a,LL b,LL &ans) {if(a == 0 ||b == 0) return ;if(a > b) swap(a,b);LL _min = a;LL d = a;LL t = abs(a-b);LL tmp = t;vector<LL> prime;for(LL i = 2;i * i <= tmp; ++i) {if(t %i == 0) {prime.push_back(i);while(t%i==0) t/= i;}}if(t > 1) prime.push_back(t);for(auto &c:prime) {if(a > c &&a%c < _min) {_min = a%c;d = c;}}ans += _min;get((a-_min)/d,(b-_min)/d,ans);
}
int main(void) {LL A,B;cin>>A>>B;LL d = gcd(A,B);A = A/d;B = B/d;LL ans = 0;get(A,B,ans);cout<<ans<<endl;return 0;
}

相关文章:

B - GCD Subtraction

文章目录 AtCoder Regular Contest 159B - GCD Subtraction AtCoder Regular Contest 159 B - GCD Subtraction 问题&#xff1a;每次A,B都减去gcd(A,B)&#xff0c;求其中一个减到0至少需要多少次主要思路&#xff1a; 首先第一步应该想到每次减去的数&#xff0c;先减去的数…...

解决Failed to load ApplicationContext问题的思路

中文翻译&#xff1a; 加载ApplicationContext失败 第一步&#xff1a;首先检查测试类的注解 以及 依赖 SpringBootTest <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-test</artifactId><scop…...

基于CAMX大气臭氧来源解析模拟与臭氧成因分析实践技术应用

查看原文>>>基于CAMX大气臭氧来源解析模拟与臭氧成因分析实践技术应用 目录 专题一、大气臭氧污染来源及成因分析技术讲解&#xff1b;CAMx模式初识及臭氧来源解析模拟本地案例配置说明 专题二、CAMx模式编译安装及空气质量模拟案例配置 专题三、CAMx扩展和探测工…...

异常的讲解 (1)

目录 异常入门的案例 异常介绍 基本概念 异常的小结 常见的运行时异常 1.NullPointerException空指针异常 2.ArithmeticException数学运算异常 3.ArraylndexOutOfBoundsException数组下标越界异常 4.ClassCastException类型转换异常 5.NumberFormatException数字格式不…...

Prometheus - Grafana 监控 MySQLD Linux服务器 demo版

目录 首先是下载Prometheus 下载和安装 配置Prometheus 查看监控数据 监控mysql demo 部署 mysqld_exporter 组件 配置 Prometheus 获取监控数据 -------------------------------------- 安装和使用Grafana 启动Grafana -------------------------------------- 配…...

应届生,实力已超6年,太卷了!

你好&#xff0c;我是田哥 今晚上&#xff0c;给一位朋友做模拟面试&#xff0c;原本说好的90分钟左右&#xff0c;结果整了2个多小时。 很多人估计也很好奇&#xff0c;我们这两个多小时聊聊什么&#xff0c;下面我给大致总结一下&#xff1a; 面试技巧 面试中&#xff0c;我们…...

0-1背包问题

文章目录 0-1背包问题JavaPython0-1背包问题 【问题描述】 给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大? 【输入形式】 第一行输入物品的个数n和背包容量C。 第二行输入每个物品的价值v[i…...

VUE前端项目环境搭建

背景&#xff1a; 想要使用vue搭建一个前端项目&#xff0c;写个小网站练练手&#xff0c;因为没有前端经验&#xff0c;所以从网上找了一个vue得开源模板使用&#xff0c;经过一番挑选选中了字节公司花裤衩大佬开源得项目&#xff0c;地址如下&#xff1a; 开源项目地址&…...

VMware安装Win2000安装程序闪退重启等问题的解决方法

VMware安装Win2000安装程序闪退重启等问题的解决方法 【症状】 1、比较新的VMware版本如16.2.5&#xff0c;Win2000安装时&#xff0c;安装程序在安装Distributed Transaction Coordinator时闪退重启 2、比较新的VMware版本如17.0.1&#xff0c;还会发生显示跳跃性卡顿的现象…...

【id:45】【20分】A. Equation(类与对象+构造)

题目描述 建立一个类Equation&#xff0c;表达方程ax2bxc0。类中至少包含以下方法&#xff1a; 1、无参构造&#xff08;abc默认值为1.0、1.0、0&#xff09;与有参构造函数&#xff0c;用于初始化a、b、c的值&#xff1b; 2、set方法&#xff0c;用于修改a、b、c的值 3、ge…...

数据库事务

什么是事务 在数据库中&#xff0c;事务&#xff08;Transaction&#xff09;是指一组数据库操作&#xff0c;这些操作要么全部成功执行&#xff0c;要么全部失败回滚&#xff0c;是保证数据库操作一致性的基本单位。事务具有原子性&#xff08;Atomicity&#xff09;、一致性…...

Macbook(苹果电脑) VSCode 创建简单c++程序 配置C++开发环境

1.打开 Terminal 终端&#xff08;Command空格&#xff0c;输入Terminal&#xff09;。 1.1 输入如下指令&#xff0c;查看是否显示版本信息。 clang --version 1.2 如果出现版本信息&#xff0c;则跳过&#xff0c;否则输入 xcode-select --install 2. 为 VS Code 安装插件 …...

如何使用 Matlab 构建深度学习模型

深度学习已经成为了AI领域的热门话题&#xff0c;相信很多人都想学习如何构建深度学习模型&#xff0c;那么&#xff0c;我们就一起来看看如何使用Matlab构建深度学习模型。 首先&#xff0c;我们需要准备好Matlab的环境。Matlab是一款非常强大的数学计算软件&#xff0c;它提…...

PDF怎么转CAD文件?(免费!高效转换方法汇总)

一般而言&#xff0c;PDF图纸是不能修改的。若需修改&#xff0c;则需将PDF转CAD&#xff0c;此时如何满足PDF转CAD的需求呢&#xff1f;今天&#xff0c;我将教你两种免费的PDF转CAD的方法&#xff0c;助力高效办公。 1.本地软件转换法 这是用本地软件转换方法&#xff0c;支…...

经历了野蛮生长之后,新科技或许已经抵达了全新的临界点

跳出仅仅只是以概念和营销的方式来定义元宇宙&#xff0c;真正找到元宇宙与现实商业之间的桥接&#xff0c;让元宇宙可以在真实实践上得到复现&#xff0c;才是保证元宇宙的发展可以进入到一个全新发展阶段的关键所在。归根到底&#xff0c;我们还是要找到元宇宙落地的正确的方…...

Segment Anything论文翻译,SAM模型,SAM论文,SAM论文翻译;一个用于图像分割的新任务、模型和数据集;SA-1B数据集

【论文翻译】- Segment Anything / Model / SAM论文 论文链接&#xff1a; https://arxiv.org/pdf/2304.02643.pdfhttps://ai.facebook.com/research/publications/segment-anything/ 代码连接&#xff1a;https://github.com/facebookresearch/segment-anything 论文翻译&…...

EMQX vs NanoMQ | 2023 MQTT Broker 对比

引言 EMQX 和 NanoMQ 都是由全球领先的开源物联网数据基础设施软件供应商 EMQ 开发的开源 MQTT Broker。 EMQX 是一个高度可扩展的大规模分布式 MQTT Broker&#xff0c;能够将百万级的物联网设备连接到云端。NanoMQ 则是专为物联网边缘场景设计的轻量级 Broker。 本文中我们…...

RabbitMQ实现消息的延迟推送或延迟发送

一、RabbitMQ是什么&#xff1f; 1.RabbitMQ简介 RabbitMQ是有erlang语言开发&#xff0c;基于AMQP&#xff08;Advanced Message Queue 高级消息队列协议&#xff09;协议实现的消息队列。 常见的消息队列有&#xff1a;RabbitMQ、Kafka 和 ActiveMQ 2.RabbitMQ的优点 Rab…...

解决python中import导入自己的包呈现灰色 无效的问题

打开File–> Setting—> 打开 Console下的Python Console&#xff0c;把选项&#xff08;Add source roots to PYTHONPAT&#xff09;点击勾选上。 右键点击需要导入的工作空间文件夹&#xff0c;找到Mark Directory as 选择Source Root。 另外&#xff0c;Python中的…...

消息中间件对比

1&#xff0c;常见消息中间件对比(后续逐个介绍) 比较项TubeMQKafkaPulsar数据时延非常低&#xff0c;10ms比较低&#xff0c;250ms非常低&#xff0c;10msTPS高&#xff0c;14W/s一般&#xff0c;10W/s高&#xff0c;14W/s (高性能场景)过滤消费支持服务端过滤和客户端过滤客…...

Stable Diffusion XL 1.0开源大模型教程:灵感画廊app.py核心逻辑解读

Stable Diffusion XL 1.0开源大模型教程&#xff1a;灵感画廊app.py核心逻辑解读 “见微知著&#xff0c;凝光成影。将梦境的碎片&#xff0c;凝结为永恒的视觉诗篇。” 如果你对AI绘画感兴趣&#xff0c;一定听说过Stable Diffusion XL 1.0这个强大的开源模型。但面对复杂的参…...

若依前后端分离系统生产环境部署:从零到上线的保姆级教程

若依前后端分离系统生产环境部署实战指南 引言&#xff1a;为什么选择若依框架&#xff1f; 对于刚接触企业级开发的新手来说&#xff0c;若依(RuoYi)框架无疑是一个绝佳的起点。这个基于Spring Boot和Vue.js的前后端分离架构&#xff0c;不仅提供了完善的权限管理、代码生成等…...

数字中国新引擎:产业经济大脑的全景式解构与深度洞察(PPT)

“中国经济高质量发展的核心命题&#xff0c;已从‘有没有’转向‘好不好’。而要回答‘好不好’&#xff0c;就必须构建一套能看清、看准、看远的‘经济慧眼’。”在数字经济成为国家战略主战场的今天&#xff0c;地方政府正面临着前所未有的治理挑战&#xff1a;宏观政策如何…...

League-Toolkit:英雄联盟玩家的智能游戏助手

League-Toolkit&#xff1a;英雄联盟玩家的智能游戏助手 【免费下载链接】League-Toolkit 兴趣使然的、简单易用的英雄联盟工具集。支持战绩查询、自动秒选等功能。基于 LCU API。 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit League-Toolkit是一款基于…...

别再只调CLIP了!用Qwen2.5-VL的‘鹰之眼’搞定高清文档解析与长视频理解

Qwen2.5-VL&#xff1a;解锁工业级多模态理解的"鹰之眼"技术 在数字化转型浪潮中&#xff0c;企业每天需要处理海量的非结构化数据——从财务报表扫描件到生产线监控视频&#xff0c;从医疗影像到用户生成内容。传统AI模型在处理这些数据时&#xff0c;往往面临两大痛…...

Comsol多重法诺共振拟合:探索与实践

comsol多重法诺共振拟合。 在光学与光子学领域&#xff0c;多重法诺共振现象一直是研究的热点。而Comsol作为一款强大的多物理场仿真软件&#xff0c;为我们研究多重法诺共振提供了有力的工具&#xff0c;尤其是其中的拟合功能&#xff0c;能够帮助我们更精准地理解和分析这一…...

手把手教你用两块STM32F103C8T6实现CAN总线点对点通信(附完整代码)

从零开始实现STM32F103C8T6双板CAN总线通信实战指南 在嵌入式开发领域&#xff0c;CAN总线因其高可靠性和实时性成为工业控制、汽车电子等场景的首选通信协议。对于初学者而言&#xff0c;使用两块STM32F103C8T6开发板搭建CAN通信系统是掌握该技术的经典入门项目。本文将彻底拆…...

SEO_移动端SEO优化的关键步骤与注意事项介绍

<h1 id"seo">移动端SEO优化的关键步骤与注意事项介绍</h1> <p>在互联网时代&#xff0c;移动端已经成为用户访问网站的主要途径。因此&#xff0c;移动端SEO优化变得尤为重要。本文将详细介绍移动端SEO优化的关键步骤与注意事项&#xff0c;帮助你…...

Python+Spark+Hadoop商品评论数据分析可视化系统+情感分析 大数据毕业设计

1、项目介绍 技术栈&#xff1a; Python语言、Django框架、MySQL数据库 、Echarts可视化、情感分析、HTML商品评论数据分析可视化系统是基于Python语言和Django框架开发的一个Web应用程序。它的主要功能是对商品评论数据进行分析&#xff0c;并将分析结果通过Echarts可视化库展…...

【BoClaw教程03】BoClaw实战:打工人常用技能

博云BoClaw官方教程系列&#xff08;三&#xff09;本教程聚焦打工人日常办公高频需求&#xff0c;详细讲解 BoClaw 在桌面整理、文档检索、PPT 制作、简历筛选、销售报表处理五大场景的实操方法、操作要点及避坑技巧&#xff0c;助力高效提升办公效率。1.桌面整理&#xff1a;…...