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

AcWing 223. 阿九大战朱最学——扩展欧几里得算法

news 来源：原创 2025/7/19 7:37:05

题目来源

223. 阿九大战朱最学 - AcWing题库

题目描述

自从朱最学搞定了 QQ 农场以后，就开始捉摸去 QQ 牧场干些事业，不仅在自己的牧场养牛，还到阿九的牧场放牛！

阿九很生气，有一次朱最学想知道阿九牧场奶牛的数量，于是阿九想狠狠耍朱最学一把。

举个例子，假如有 1616 头奶牛，如果建了 33 个牛棚，剩下 11 头牛就没有地方安家了。

如果建造了 55 个牛棚，但是仍然有 11 头牛没有地方去，然后如果建造了 77 个牛棚，还有 22 头没有地方去。

你作为阿九的私人秘书理所当然要将准确的奶牛数报给阿九，你该怎么办？

输入格式

第一行包含一个整数 n表示建立牛棚的次数。

接下来 n行，每行两个整数 ai,bi，表示建立了 ai 个牛棚，有 bi 头牛没有去处。

你可以假定不同 ai 之间互质。

输出格式

输出包含一个正整数，即为阿九至少养奶牛的数目。

数据范围

1≤n≤101≤≤10,
1≤ai,bi≤12000001≤1200000，
所有 ai 的乘积不超过 10121012。

输入样例：

输出样例：

算法分析

中国剩余定理的经典题；

这道题可以列出方程组，只需计算

其步骤为：

1.计算模数的乘积：M=m1m2......mk;

2.对每个模数mi,计算Mi=M/mi;

3.对每个Mi求解Mi在模mi的逆元yi，即满足Mi*yi同余1模mi；

4.最终解x为：x=∑ai*Mi*yi(mod M),i∈(1,k)，其中ai是每个同余方程的余数

Code

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=1005;
LL m[N],a[N];LL exgcd(LL a,LL b,LL &x,LL &y) {//十年Oi一场空，不开longlong见祖宗if(b==0) {x=1,y=0;return a;}LL d=exgcd(b,a%b,y,x);y-=(a/b)*x;return d;
}int main() {int n;cin>>n;LL M=1;for(int i=1; i<=n; i++) {cin>>m[i]>>a[i];M*=m[i];}LL t=0;for(int i=1; i<=n; i++) {LL x,y;LL Mi=M/m[i];exgcd(Mi,m[i],x,y);t=(t+a[i]*Mi%M*x)%M;//按照分析过程进行处理}t=(t+M)%M;cout<<t<<endl;return 0;
}

AcWing 223. 阿九大战朱最学——扩展欧几里得算法

题目来源 223. 阿九大战朱最学 - AcWing题库题目描述自从朱最学搞定了 QQ 农场以后，就开始捉摸去 QQ 牧场干些事业，不仅在自己的牧场养牛，还到阿九的牧场放牛！ 阿九很生气，有一次朱最学想知道阿九牧场奶牛的数量…...

编程日记 2025/7/19 7:37:05

开发指南116-font-size: 0的使用

平台前台的css样式里有几个地方用到了font-size: 0，这是个使用小技巧。原理说明：font-size 属性用于定义元素中文本的大小。当设置 font-size: 0 时，意味着该元素内的文本将不占据空间。当元素的 font-size 设置为零时，该元素内的…...

编程日记 2025/7/1 10:37:57

算法-数对的使用

1、数对可用于数组排序中，并且可记忆化排序前的元素下标 #include<iostream> #include<string> #include<bits/stdc.h> using namespace std; typedef long long ll; const int N 2e5 10; pair<int, int> a[N]; void solve() {ll n;cin …...

编程日记 2025/7/17 22:08:54

EmoBox：我与 CodeBuddy 共创的 Emoji 表情分类小工具

我正在参加CodeBuddy「首席试玩官」内容创作大赛，本文所使用的 CodeBuddy 免费下载链接：腾讯云代码助手 CodeBuddy - AI 时代的智能编程伙伴最近我萌生了一个想法，想做一个小而美的工具——一个叫「EmoBox」的 emoji 表情分类应用&#xff0…...

编程日记 2025/7/18 22:31:25

力扣HOT100之二叉树：199. 二叉树的右视图

这道题没啥好说的，首先定义一个向量来保存每一层的最后一个元素，直接用层序遍历（广度优先搜索）遍历二叉树，然后将每一层的最后一个元素加入到这个向量中即可。属于是二叉树层序遍历的模板题。 /*** Definition for a …...

编程日记 2025/7/18 19:59:52

力扣992做题笔记

左神做法的理论依据我们可以通过集合的包含关系和具体示例枚举来直观理解这一推导过程。以下结合题目示例 1 进行详细说明： 示例 1 分析输入：nums [1,2,1,2,3], k 2 目标：计算恰好包含 2 种不同整数的子数组个数。步骤一集合 A…...

编程日记 2025/7/17 1:08:42

特征值与特征向量的计算——PCA的数学基础

特征值与特征向量定义令 A {\bm A} A为 n n n \times n nn矩阵，如果存在非零向量 x {\bm x} x使得 A x λ x (1) {\bm A}{\bm x} \lambda {\bm x}\tag{1} Axλx(1) 成立，则称数 λ \lambda λ是矩阵 A {\bm A} A的特征值，称非零向量 x…...

编程日记 2025/7/16 20:27:40

vue2.0 的计算属性

个人简介 👨‍💻‍个人主页： 魔术师 📖学习方向： 主攻前端方向，正逐渐往全栈发展 🚴个人状态： 研发工程师，现效力于政务服务网事业 🇨🇳人生格言&…...

编程日记 2025/7/18 13:58:42

缘由程序设计 -- 数根（2）-编程语言-CSDN问答 void 数根() {//缘由https://ask.csdn.net/questions/7635593?spm1005.2025.3001.5141std::string n;int m 0, a 0;std::cin >> n;while (n[a] ! \0)m n[a] - 0;a 0;while (m)a m - m / 10 * 10…...

编程日记 2025/7/16 17:04:49

【Android】一键创建Keystore + Keystore 参数说明 + 查询SHA256（JDK Keytool Keystore）

一键创建 Android Keystore 的实用方法与参数详解在 Android 应用开发与发布中，**Keystore（签名文件）**扮演着至关重要的角色。本文将介绍如何通过 .bat 脚本一键创建 Keystore 文件，并详细讲解每一个参数的含义，帮助…...

编程日记 2025/7/1 10:37:38

laravel 通过Validator::make验证后，如何拿到验证后的值

在 Laravel 中，通过 Validator::make 创建的验证器实例验证数据后，可以通过以下方式获取验证后的值： 使用 validate() 方法调用验证器实例的 validate() 方法，会返回经过验证的数据数组。如果验证失败，该方法会抛出 V…...

编程日记 2025/7/1 10:37:35

centos把jar包配置成服务并设置开机自启

1.准备好jar包，启动路径，日志路径 2.编写启动脚步 vim /etc/systemd/system/test.service [Unit] Descriptionlapis Requiresnetwork.target remote-fs.target ##启动优先级，在下面的服务之后启动 Afterkafka.service zookeeper.service n…...

编程日记 2025/7/15 10:02:24

CentOS相关操作hub（更新中）

CentOS介绍： CentOS（Community Enterprise Operating System）是基于 Red Hat Enterprise Linux（RHEL）源代码编译的开源企业级操作系统，提供与 RHEL 二进制兼容的功能完全兼容 RHEL，可直接使用…...

编程日记 2025/7/18 13:19:04

数据库（一）：分布式数据库

定义分布式数据库（Distributed Database） 是指： 数据分布在多个物理位置，但对用户透明，表现为一个统一逻辑数据库的系统。结构模式（三层模式扩展） 层次作用对应实体用户层提供统一视图&…...

编程日记 2025/7/17 4:31:32

人工智能（AI）与BIM：建筑业创新实践的深度融合

一、BIM在建筑领域的发展现状与挑战作为建筑数字化的核心技术，BIM通过三维模型集成建筑全生命周期信息，已成为工程设计、施工及运维的标准工作流程。当前，BIM在碰撞检测、施工模拟、成本管控等场景的应用已较为成熟，但行业仍面临…...

编程日记 2025/7/17 6:26:20

FIR数字滤波器设计与实现

低通滤波器的设计与实现打开Matlab ,运行命令filterDesigner，选择FIR 最小二乘或者其它，设置采样频率，和低通滤波器截止频率。点击设计滤波器，如图1： 点击目标生成.C头文件，滤波器系数如下： …...

编程日记 2025/7/18 11:41:55

软件架构之-论高并发下的可用性技术

论高并发下的可用性技术摘要正文摘要 ;2023年2月，本人所在集团公司承接了长三角地区某省渔船图纸电子化审查系统项目开发，该项目旨在为长三角地区渔船建造设计院、以及渔船审图机构提供一个便捷化的服务平台。在此项目中，我作为项目组成员参与了项目建设工作，并担任系统架…...

编程日记 2025/7/1 10:37:17

阻塞队列：线程安全与生产者消费者模型解析

一、阻塞队列阻塞队列就是基于普通队列做出扩展 1.线程安全的如果针对一个已经满了的队列进行入队列，此时入队列操作就会阻塞，一直阻塞到队列不满（其他线程出队列元素）之后如果针对一个已经空了的队列进行出队列&#xff0c…...

编程日记 2025/7/16 11:45:02

【时时三省】(C语言基础)用函数实现模块化程序设计

山不在高，有仙则名。水不在深，有龙则灵。 ----CSDN 时时三省为什么要用函数？ 已经能够编写一些简单的C程序，但是如果程序的功能比较多，规模比较大，把所有的程序代码都写在一个主函数(main函数)中&#x…...

编程日记 2025/7/17 4:31:35

基于CATIA参数化圆锥建模的自动化插件开发实践——NX建模之圆锥体命令的参考与移植（一）

引言在CATIA二次开发领域，Python因其灵活性和丰富的库支持逐渐成为高效工具开发的首选语言。本文将以笔者开发的CATIA锥体自动化建模工具为例，参考NX软件中高效锥体创建命令，深度解析基于PySide6 GUI框架与pycatia接口库的集成…...

编程日记 2025/7/17 1:26:56

天才简史——Paolo Fiorini与他的速度障碍法

一、背景第一次“认识”Paolo Fiorini教授是看了DMP的体积避障论文《Dynamic Movement Primitives: Volumetric Obstacle Avoidance》，而且他的学生Michele Ginesi将相关代码开源了，后来查阅了Paolo Fiorini相关资料才发现他竟然是速度障碍法的作者&am…...

编程日记 2025/7/18 4:46:43

第五天的尝试

目录一、每日一言二、练习题三、效果展示四、下次题目五、总结一、每日一言毅力是永久的享受。没有人是一座孤岛，每个人都是这块大陆的一部分。二、练习题 import numpy as np import matplotlib.pyplot as plt array np.array([1,2,3,4,5]) plt.plot…...

编程日记 2025/7/5 19:41:38

大小端模式和消息的加密解密

大小端模式知识点一什么是大小端模式 // 大端模式 // 是指数据的高字节保存在内存的低地址中 // 而数据的低字节保存在内存的高地址中 // 这样的存储模式有点儿类似于把数据当作字符串顺序处理 // 地址由小向大增加，数据从高位往低位放 …...

编程日记 2025/7/18 8:03:09

(1) 查看端口状态

1. lsof 和 netstat 命令的区别 1.1 lsof 概念：只有在 root 的命令下才能执行，否则无内容显示；root 命令下显示完全 lsof -i: 8080 1.2 netstat 普通用户下显示不完全，root 命令下显示完全 netstat -tunlp | grep 8080 1.3…...

编程日记 2025/7/18 8:01:13

【C++]string模拟实现

#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> #include<assert.h> using namespace std; namespace liu {class string{public:using iterator char*;using const_iterator const char*;//string();//无参构造 string(const string&…...

编程日记 2025/7/18 20:15:43

Linux动静态库制作与原理

什么是库库是写好的现有的，成熟的，可以复用的代码。现实中每个程序都要依赖很多基础的底层库，不可能每个人的代码都从零开始，因此库的存在意义非同寻常。本质上来说库是一种可执行代码的二进制形式，可以被操作系统…...

编程日记 2025/7/1 11:59:46

ArkUI Tab组件开发深度解析与应用指南

ArkUI Tab组件开发深度解析与应用指南一、组件架构与核心能力 ArkUI的Tabs组件采用分层设计结构，由TabBar（导航栏）和TabContent（内容区）构成，支持底部、顶部、侧边三种导航布局模式。组件具备以下核心特…...

编程日记 2025/7/18 23:45:57

winrar 工具测试下载与安装

https://zhuanlan.zhihu.com/p/680852417 https://www.angusj.com/resourcehacker/#download 点击String Table，在展开列表中找到80:2052展开，删除1277行。点击右上方编译按钮，并保存。...

编程日记 2025/7/17 5:51:40

代码随想录算法训练营第四十四天

卡码网题目: 99. 岛屿数量100. 岛屿的最大面积其他: 今日总结往期打卡 99. 岛屿数量跳转: 99. 岛屿数量学习: 代码随想录公开讲解问题: 给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水…...

编程日记 2025/7/17 5:19:24

每日Prompt：自拍生成摇头娃娃

提示词将这张照片变成一个摇头娃娃：头部稍微放大，保持面部准确，身体卡通化。[把它放在书架上]。...

编程日记 2025/7/18 10:47:08

制作我的计算器

1. 界面布局新建项目 MyCalculator，开始布局。 2. 静态布局代码如下： // etc/pages/Index.ets Entry Component struct Index {build() {Column() {/*** 运算区*/Column() {TextInput({ text: 12x13 }).height(100%).fontSize(32).enabled(false).f…...

编程日记 2025/7/17 1:27:03

如何查看 Ubuntu开机是否需要密码

要查看 Ubuntu 开机是否需要密码，可以通过以下方法进行判断： 1. 检查自动登录设置图形界面操作： 进入系统设置（Settings）→ 用户账户（User Accounts）→ 解锁设置（输入当前用户密码…...

编程日记 2025/7/17 8:38:18

今日行情明日机会——20250519

上证指数缩量收十字星，个股涨多跌少，这周反弹的概率比较大。深证指数缩量调整，临近反弹，个股表现更好。 2025年5月19日涨停股主要行业方向分析并购重组（政策驱动资产整合） • 涨停家数：16…...

编程日记 2025/7/18 21:02:36

【CodeBuddy 】从0到1，让网页导航栏变为摸鱼神器

【CodeBuddy 】从0到1，让网页导航栏变为摸鱼神器我正在参加CodeBuddy「首席试玩官」内容创作大赛，本文所使用的 CodeBuddy 免费下载链接：腾讯云代码助手 CodeBuddy - AI 时代的智能编程伙伴 🌟嗨，我是LucianaiB&#…...

编程日记 2025/7/17 17:18:32

PCL点云库点云数据处理入门系列教材目录（2025年5月更新....）

PCL点云库点云数据处理入门系列教材目录基础阶段第 1 讲：PCL库简介和安装（Win10/11VS2019PCL 1.12.0）第 2 讲：PCL库中点云基本知识和数据类型结构第 3 讲：PCL库中点云数据格式PCD和PLY及其输入输出（IO&…...

编程日记 2025/7/17 8:01:11

同一颗太阳：Australia、Austria、Arab、Africa、Augustus、August、Aurora、Athena

我们来看一下下面这一堆单词： Australia n.澳大利亚；澳洲 Australian n.澳大利亚人 a.澳大利亚的 Austria n.奥地利 Austrian n.奥地利人 a.奥地利(人)的 Africa n.非洲 African n.非洲人* Arab a.阿拉伯的；阿拉伯人的 n.阿拉伯人(pl.Arabs)…...

编程日记 2025/7/17 7:13:45

用户账号及权限管理：企业安全的基石与艺术

在当今数字化时代，用户账号及权限管理已成为企业IT安全体系中不可或缺的核心组件。它不仅是保护敏感数据的第一道防线，更是确保业务运营效率和合规性的关键。本文将深入探讨用户账号及权限管理的重要性、最佳实践以及实施策略，助您构建一个安全、高效且灵活的访问控制体系。…...

编程日记 2025/7/18 17:51:18

存储系统03——数据缓冲evBuffer

存储系统03——数据缓冲evBuffer 数据缓冲evBuffer分段存储零拷贝线程安全 evbuffer 实例——存储系统事件触发数据缓冲evBuffer evbuffer 是 Libevent 提供的一个高效内存缓冲区管理工具，用于存储和操作数据。它类似于一个动态增长的字节缓冲区，支持多…...

编程日记 2025/7/1 11:59:21

留给王小川的时间不多了

王小川，这位头顶“天才少年”光环的清华学霸、搜狗输入法创始人、中国互联网初代技术偶像，正迎来人生中最难啃的硬骨头。他在2023年创立的百川智能，被称为“大模型六小虎”之一。今年4月，王小川在全员信中罕见地反思过去两年工作…...

编程日记 2025/7/1 11:59:19

Python海龟绘图-斗地主

#导入库 import random as r import turtle as t #数据 pk[红心A,红心2,红心3,红心4,红心5,红心6,红心7,红心8, 红心9,红心10,红心J,红心Q,红心K,黑桃A,黑桃2,黑桃3,黑桃4,黑桃5,黑桃6,黑桃7,黑桃8, 黑桃9,黑桃10,黑桃J, 黑桃Q,黑桃K,方块A,方块2,方块3,方块4,方块5,方块6,方块…...

编程日记 2025/7/17 10:09:50

一、内存调优

一、内存调优什么是内存泄漏监控Java内存的常用工具内存泄露的常见场景内存泄露的解决方案内存泄露与内存溢出的区别内存泄露：在Java中如果不再使用一个对象，但是该对象依然在GC ROOT的引用链上，这个对象就不会被垃圾回收器回收&…...

编程日记 2025/7/17 1:27:24

机器学习--特征工程具体案例

一、数据集介绍 sklearn库中的玩具数据集，葡萄酒数据集。在前两次发布的内容《机器学习基础中》有介绍。 1.1葡萄酒列标签名： wine.feature_names 结果： [alcohol, malic_acid, ash, alcalinity_of_ash, magnesium, total_phenols, flavanoi…...

编程日记 2025/7/17 12:33:40

Java-List集合类全面解析

Java-List集合类全面解析前言一、List接口概述与核心特性1.1 List在集合框架中的位置1.2 List的核心特性1.3 常见实现类对比二、ArrayList源码剖析与应用场景2.1 内部结构与初始化2.2 动态扩容机制2.3 性能特点与最佳实践三、LinkedList 源码剖析与应用场景3.1 内部结构与节…...

编程日记 2025/7/1 11:59:11

在Cursor中启用WebStorm/IntelliJ风格快捷键

在Cursor中启用WebStorm/IntelliJ风格快捷键方法一：使用预置快捷键方案打开快捷键设置 Windows/Linux: Ctrl K → Ctrl SmacOS: ⌘ K → ⌘ S 搜索预设方案在搜索框中输入keyboard shortcuts，选择Preferences: Open Keyboard Shortcuts (JSON) …...

编程日记 2025/7/17 5:36:20

32、跨平台咒语—— React Native初探

一、时空晶体架构（核心原理） 1. 量子组件桥接协议 // 原生组件映射 <View> → iOS UIView / Android ViewGroup <Text> → UILabel / TextView 魔法特性： • JavaScriptCore引擎：通过V8/Hermes引擎执行JS逻辑…...

编程日记 2025/7/1 11:59:07

无源探头衰减比与带宽特性的关联性研究

引言在电子测量领域，无源探头作为示波器的重要附件，其性能参数直接影响测量结果的准确性。本文将从电路设计原理出发，深入分析衰减比与带宽这两个关键参数的相互关系，帮助工程师正确理解并选择适合的测量探头。技术原理分析 …...

编程日记 2025/7/1 11:59:06

虚拟机的三个核心类加载器

虚拟机的三个核心类加载器在Java虚拟机（JVM）中，类加载器（ClassLoader）负责将类的字节码加载到内存中，并生成对应的Class对象。以下是三个核心类加载器的详细说明： 1. 启动类加载器（Bootstrap ClassLoader）职责：加载Java核心类库（如java.lang、java.util等），位…...

编程日记 2025/7/1 11:59:04