当前位置: 首页 > 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;尤…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...

什么是VR全景技术

VR全景技术&#xff0c;全称为虚拟现实全景技术&#xff0c;是通过计算机图像模拟生成三维空间中的虚拟世界&#xff0c;使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验&#xff0c;结合图文、3D、音视频等多媒体元素…...