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,对于每对数,求出一组ai ,g,使其满足ai* xi bi * yi gcd(ai ,bi)。 输入格式 第一行包含整数n。 接下来n行,每行包含两个整数ai , bi。 输出格式 输出共n行,对于每组ai, bi,…...
基于自组织竞争网络的患者癌症发病预测(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.部署模型 如何高效实现垂直大模型 ✍创作者:全栈弄潮儿 🏡 个人主页…...
Maven可选依赖和排除依赖简单使用
可选依赖 可选依赖指对外隐藏当前所依赖的资源 在maven_04_dao的pom.xml,在引入maven_03_pojo的时候,添加optional <dependency><groupId>com.rqz</groupId><artifactId>maven_03_pojo</artifactId><version>1.0-SNAPSHOT&…...
“深入探索JVM:Java虚拟机的工作原理解析“
标题:深入探索JVM:Java虚拟机的工作原理解析 摘要:本文将深入探索Java虚拟机(JVM)的工作原理,从类加载、内存管理、垃圾回收、即时编译器等方面进行详细解析,帮助读者更好地理解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.点进去,在app.json里面配置 在你需要的 页面的 json里面配置,按需引入 然后看文档,再在你的 wxml里面使用就好了...
git目录初始化,并拉取最新代码
现有C:\data目录,将目录初始化,并拉取代码在这里插入代码片 https://gitlab.arsbaibaodun.com/bcx_v5_app/baoan-hangyedcjg.git 1、 git init生成 .git 目录即目录初始化完成,可以进行拉取代码 代码成功拉取到了data目录,默认…...
运筹调度算法工程式招聘情况:技能要求、薪资、工作地
目录 一、前言二、岗位信息三、总结 一、前言 前一段时间,常看到运筹学的老师们在朋友圈转发下面的图片。今天忽然想起这件事,顺势查了一下“调度算法工程师”在Boss直聘上的岗位信息,也整理一下招聘企业所需的“调度”技能。 二、岗位信息…...
css2-BFC是什么?
1、BFC是什么? 在页面布局时,经常会出现以下几种情况: 这个元素高度怎末没了? 这两栏布局怎末没法自适应? 这两个元素的间距怎末有点奇怪的样子? … 原因就是元素之间互相影响,导致了意料之外的…...
Flutter Dart语言(04)库操作
0 说明 该系列教程主要是为有一定语言基础 C/C的程序员,快速学习一门新语言所采用的方法,属于在C/C基础上扩展新语言的模式。 1 自定义库 & 系统自定义库 引入代码如下所示: import xxx.dart; //自定义库引入,xxx为本…...
通向架构师的道路之漫谈使用ThreadLocal改进你的层次的划分
一、什么是ThreadLocal 早在JDK 1.2的版本中就提供java.lang.ThreadLocal,ThreadLocal为解决多线程程序的并发问题提供了一种新的思路。使用这个工具类可以很简洁地编写出优美的多线程程序。 ThreadLocal很容易让人望文生义,想当然地认为是一个“本地线…...
springboot全局统一返回处理
文章目录 前言一、统一的返回格式二、全局异常处理三、全局返回处理(装逼用的)总结 前言 项目中一般都会有规定好的接口返回格式,无论成功与失败,一般格式都是不变的,这样是为了方便前后端统一处理,今天就来说下前后端统一处理的较为优雅的方式; 一、统一的返回格式 一般而言…...
C/C++面试经历(一)
目录 1. 说说你对C与C的认识? 2. 说说C的三大特性? 3. 说说C的重载? 4. C语言为什么不支持重载? 5. 说说类的默认成员函数? 6. 类的构造函数为什么不支持虚函数? 7. 说说你对指针和引用的理解&…...
【PostgreSQL】系列之 一 用户创建和授权(三)
🍁 博主 "开着拖拉机回家"带您 Go to New World.✨🍁 🦄 个人主页——🎐开着拖拉机回家_Linux,Java基础学习,大数据运维-CSDN博客 🎐✨🍁 🪁🍁 希望本文能够给您带来一定的…...
Python连接Hive实例教程
一 Python连接hive环境实例 经在网络查询相关的教程,发现有好多的例子,发现连接底层用的的驱动基本都是pyhive和pyhs2两种第三方库的来连接的 hive,下面将简介windows 10 python 3.10 连接hive的驱动程序方式,开发工具:pycharm …...
Jest和Mocha对比:两者之间有哪些区别?
目录 什么是单元测试? Jest和Mocha介绍 Jest Jest的特点: Jest的使用限制 Mocha Mocha的特点 使用Mocha的限制 Jest和Mocha的全面比较 我们应该使用哪个测试框架? 结论 什么是单元测试? 所谓单元测试,是对软…...
Oracle:merge into用法
文章目录 merge into使用场景merge into语法测试表普通模式 merge使用注意点 merge into MERGE 是 Oracle9i 新增的语法,根据源表对目标表进行匹配查询,匹配成功时更新,不成功时插入 比单独的 update insert 的方式效率要更高,尤…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
