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

Acwing.877 扩展欧几里得算法

题目

给定n对正整数ai , bi,对于每对数,求出一组ai ,g,使其满足ai* xi+ bi * yi = gcd(ai ,bi)。

输入格式

第一行包含整数n。
接下来n行,每行包含两个整数ai , bi。

输出格式

输出共n行,对于每组ai, bi,求出一组满足条件的axi, Ji,每组结果占一行。本题答案不唯一,输出任意满足条件的xi,yi均可。

数据范围

1 ≤n≤105,
1≤ai,bi≤ 2* 109

  • 输入样例:
2
4 6
8 18
  • 输出样例
-1 1
-2 1

题解

#include <iostream>
using namespace std;
int exgcd(int a,int b,int &x, int &y)
{if (!b){	x = 1, y = 0;return a;		}int d = exgcd(b,a % b, y, x);y -= a / b * x;return d;
}	
int main( )
{int n;scanf("%d",&n);while (n -- ){int a, b, x,y;scanf("%d%d", &a,&b);exgcd(a,b,x,y);printf("%d %d\n", x, y);}	return 0;

思路

在欧几里得算法的基础上进行公式推导
具体推导如下图
在这里插入图片描述

相关文章:

Acwing.877 扩展欧几里得算法

题目 给定n对正整数ai , bi&#xff0c;对于每对数&#xff0c;求出一组ai ,g&#xff0c;使其满足ai* xi bi * yi gcd(ai ,bi)。 输入格式 第一行包含整数n。 接下来n行&#xff0c;每行包含两个整数ai , bi。 输出格式 输出共n行&#xff0c;对于每组ai, bi&#xff0c…...

基于自组织竞争网络的患者癌症发病预测(matlab代码)

1.案例背景 1.1自组织竞争网络概述 前面案例中讲述的都是在训练过程中采用有导师监督学习方式的神经网络模型。这种学习方式在训练过程中,需要预先给网络提供期望输出,根据期望输出来调整网络的权重,使得实际输出和期望输出尽可能地接近。但是在很多情况下,在人们认知的过程中…...

golang mongodb

看代码吧 package main// 链接案例 https://www.mongodb.com/docs/drivers/go/current/fundamentals/connection/#connection-example // 快速入门 https://www.mongodb.com/docs/drivers/go/current/quick-start/ import ("context""fmt""log"…...

docker中的jenkins去配置sonarQube

docker中的jenkins去配置sonarQube 1、拉取sonarQube macdeMacBook-Pro:~ mac$ docker pull sonarqube:8.9.6-community 8.9.6-community: Pulling from library/sonarqube 8572bc8fb8a3: Pull complete 702f1610d53e: Pull complete 8c951e69c28d: Pull complete f95e4f8…...

企业如何实现自己的AI垂直大模型

文章目录 为什么要训练垂直大模型训练垂直大模型有许多潜在的好处训练垂直大模型也存在一些挑战 企业如何实现自己的AI垂直大模型1.确定需求2.收集数据3.准备数据4.训练模型5.评估模型6.部署模型 如何高效实现垂直大模型 ✍创作者&#xff1a;全栈弄潮儿 &#x1f3e1; 个人主页…...

Maven可选依赖和排除依赖简单使用

可选依赖 可选依赖指对外隐藏当前所依赖的资源 在maven_04_dao的pom.xml,在引入maven_03_pojo的时候&#xff0c;添加optional <dependency><groupId>com.rqz</groupId><artifactId>maven_03_pojo</artifactId><version>1.0-SNAPSHOT&…...

“深入探索JVM:Java虚拟机的工作原理解析“

标题&#xff1a;深入探索JVM&#xff1a;Java虚拟机的工作原理解析 摘要&#xff1a;本文将深入探索Java虚拟机&#xff08;JVM&#xff09;的工作原理&#xff0c;从类加载、内存管理、垃圾回收、即时编译器等方面进行详细解析&#xff0c;帮助读者更好地理解JVM的内部机制。…...

Prometheus-各种exporter

文章目录 一、 nginx-prometheus-exporter1 nginx 配置1.1 Nginx 模块支持1.2 Nginx 配置文件配置2 部署 nginx-prometheus-exporter2.1 二进制方式部署2.1.1 解压部署2.1.2 配置 systemd2.1.3 添加 prometheus 的配置2.1.4 Dashborad2.2 docker-compose 方式部署3 可配置的指标…...

小程序的 weiui的使用以及引入

https://wechat-miniprogram.github.io/weui/docs/quickstart.html 网址 1.点进去&#xff0c;在app.json里面配置 在你需要的 页面的 json里面配置&#xff0c;按需引入 然后看文档&#xff0c;再在你的 wxml里面使用就好了...

git目录初始化,并拉取最新代码

现有C:\data目录&#xff0c;将目录初始化&#xff0c;并拉取代码在这里插入代码片 https://gitlab.arsbaibaodun.com/bcx_v5_app/baoan-hangyedcjg.git 1、 git init生成 .git 目录即目录初始化完成&#xff0c;可以进行拉取代码 代码成功拉取到了data目录&#xff0c;默认…...

运筹调度算法工程式招聘情况:技能要求、薪资、工作地

目录 一、前言二、岗位信息三、总结 一、前言 前一段时间&#xff0c;常看到运筹学的老师们在朋友圈转发下面的图片。今天忽然想起这件事&#xff0c;顺势查了一下“调度算法工程师”在Boss直聘上的岗位信息&#xff0c;也整理一下招聘企业所需的“调度”技能。 二、岗位信息…...

css2-BFC是什么?

1、BFC是什么&#xff1f; 在页面布局时&#xff0c;经常会出现以下几种情况&#xff1a; 这个元素高度怎末没了&#xff1f; 这两栏布局怎末没法自适应&#xff1f; 这两个元素的间距怎末有点奇怪的样子&#xff1f; … 原因就是元素之间互相影响&#xff0c;导致了意料之外的…...

Flutter Dart语言(04)库操作

0 说明 该系列教程主要是为有一定语言基础 C/C的程序员&#xff0c;快速学习一门新语言所采用的方法&#xff0c;属于在C/C基础上扩展新语言的模式。 1 自定义库 & 系统自定义库 引入代码如下所示&#xff1a; import xxx.dart; //自定义库引入&#xff0c;xxx为本…...

通向架构师的道路之漫谈使用ThreadLocal改进你的层次的划分

一、什么是ThreadLocal 早在JDK 1.2的版本中就提供java.lang.ThreadLocal&#xff0c;ThreadLocal为解决多线程程序的并发问题提供了一种新的思路。使用这个工具类可以很简洁地编写出优美的多线程程序。 ThreadLocal很容易让人望文生义&#xff0c;想当然地认为是一个“本地线…...

springboot全局统一返回处理

文章目录 前言一、统一的返回格式二、全局异常处理三、全局返回处理(装逼用的)总结 前言 项目中一般都会有规定好的接口返回格式,无论成功与失败,一般格式都是不变的,这样是为了方便前后端统一处理,今天就来说下前后端统一处理的较为优雅的方式; 一、统一的返回格式 一般而言…...

C/C++面试经历(一)

目录 1. 说说你对C与C的认识&#xff1f; 2. 说说C的三大特性&#xff1f; 3. 说说C的重载&#xff1f; 4. C语言为什么不支持重载&#xff1f; 5. 说说类的默认成员函数&#xff1f; 6. 类的构造函数为什么不支持虚函数&#xff1f; 7. 说说你对指针和引用的理解&…...

【PostgreSQL】系列之 一 用户创建和授权(三)

&#x1f341; 博主 "开着拖拉机回家"带您 Go to New World.✨&#x1f341; &#x1f984; 个人主页——&#x1f390;开着拖拉机回家_Linux,Java基础学习,大数据运维-CSDN博客 &#x1f390;✨&#x1f341; &#x1fa81;&#x1f341; 希望本文能够给您带来一定的…...

Python连接Hive实例教程

一 Python连接hive环境实例 经在网络查询相关的教程&#xff0c;发现有好多的例子&#xff0c;发现连接底层用的的驱动基本都是pyhive和pyhs2两种第三方库的来连接的 hive,下面将简介windows 10 python 3.10 连接hive的驱动程序方式&#xff0c;开发工具&#xff1a;pycharm …...

Jest和Mocha对比:两者之间有哪些区别?

目录 什么是单元测试&#xff1f; Jest和Mocha介绍 Jest Jest的特点&#xff1a; Jest的使用限制 Mocha Mocha的特点 使用Mocha的限制 Jest和Mocha的全面比较 我们应该使用哪个测试框架&#xff1f; 结论 什么是单元测试&#xff1f; 所谓单元测试&#xff0c;是对软…...

Oracle:merge into用法

文章目录 merge into使用场景merge into语法测试表普通模式 merge使用注意点 merge into MERGE 是 Oracle9i 新增的语法&#xff0c;根据源表对目标表进行匹配查询&#xff0c;匹配成功时更新&#xff0c;不成功时插入 比单独的 update insert 的方式效率要更高&#xff0c;尤…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

前言&#xff1a;本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中&#xff0c;跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南&#xff0c;你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案&#xff0c;并结合内网…...

网页端 js 读取发票里的二维码信息(图片和PDF格式)

起因 为了实现在报销流程中&#xff0c;发票不能重用的限制&#xff0c;发票上传后&#xff0c;希望能读出发票号&#xff0c;并记录发票号已用&#xff0c;下次不再可用于报销。 基于上面的需求&#xff0c;研究了OCR 的方式和读PDF的方式&#xff0c;实际是可行的&#xff…...