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

ACM数论 裴蜀定理(贝祖定理)

一.内容定义

        「裴蜀定理」,又称贝祖定理(Bézout's lemma)。是一个关于最大公约数的定理。其内容定义为:对于不全为零的任意整数 a 和 b,记二者的最大公约数为 g 即 gcd(a,b) = g,则对于任意整数 x 和 y 都一定满足 ax+by 是 g 的倍数。特别地,一定存在整数 x 和 y 的解,使得 ax+by=gcd(a,b) 成立。它的一个重要推论为:a,b互质充分必要条件是存在整数x,y 使 ax+by=1; 或者说对于方程 ax+by=1 只有整数a和b互质时,方程才有整数解x,y。

        「裴蜀定理」也可以推广到多个整数的情况。对于不全为零的任意 n 个整数 a_1,a_2,a_3,...,a_n,记这 n 个数的最大公约数为 g = gcd(a_1,a_2,...,a_n) ,则对于任意 n 个整数 x_1,x_2,...,x_n 都满足 \sum_{1}^{n} a_i*x_i 是 g 的倍数。特别的,一定存在一个整数序列的解 x_1,x_2,...,x_n 使得 x_1*a_1+x_2*a_2+...+x_n*a_n = g 成立。 它的一个重要的推论为:正整数 ​a_1 到 a_n​ 的最大公约数是 1 充分必要条件是存在 n 个整数 x_1 到 x_n 满足 x_1*a_1+x_2*a_2+...+x_n*a_n = 1

二.证明与应用

1.证明

        裴蜀定理的证明在本文就不再赘述,该定理是一个很简单但是又非常重要的基本定理。这里给出两个比较官方的证明,请参考如下:

  • 「裴蜀定理」百度百科
  • 「裴蜀定理」OI Wiki

2.应用

        裴蜀定理作为一个非常重要的基本定理,一方面可以在一些算法题目中作为关键的解题思路出现;另一方面,该定理也是一些算法和证明的推导基础,比如 扩展欧几里得算法、线性同余方程等。可以参考我之前的文章会更加清晰:

  • 「扩展欧几里得算法」CSDN BLOG

三.例题

1.「检查好数组」LeetCode 1250

        给你一个正整数数组 nums,你需要从中任选一些子集,然后将子集中每一个数乘以一个 任意整数,并求出他们的和。假如该和结果为 1,那么原数组就是一个「好数组」,则返回 True;否则请返回 False。

        原题要求可以转换为求在数组中是否存在 x_1*nums_1 + x_2*nums_2 +... + x_k*nums_k = 1 ,根据裴蜀定理可知,该问题即为求解数组中是否存在任意一组互质的数。

         正面去思考的话问题比较复杂,我们需要考虑是否存在两两互质、三个互质 ...,时间复杂度较高。但是从反面去思考的话问题就简单很多:一个数组要么是「好数组」,要么就是「非好数组」;如果整个数组是「非好数组」,就意味着数组中不存在任意一组互质的数(任意两两都不互质),那么我们直接求整个数组 nums_1,nums_2,....,nums_n 的最大公约数即可。若全部数字的最大公约数等于 1 则原数组为「好数组」,否则不是。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;class Solution {
public:int gcd(int a,int b){return b==0?a:gcd(b,a%b);}bool isGoodArray(vector<int>& nums) {int len = nums.size();int x = nums[0];for(int i = 1;i<len;i++){if(x==1)break;x = gcd(x,nums[i]);}return x == 1;}
};

相关文章:

ACM数论 裴蜀定理(贝祖定理)

一.内容定义 「裴蜀定理」&#xff0c;又称贝祖定理&#xff08;Bzouts lemma&#xff09;。是一个关于最大公约数的定理。其内容定义为&#xff1a;对于不全为零的任意整数 a 和 b&#xff0c;记二者的最大公约数为 g 即 gcd(a,b) g&#xff0c;则对于任意整数 x 和 y 都一定…...

基础篇—CSS Position(定位)解析

CSS Position(定位) position 属性指定了元素的定位类型。 position 属性的五个值: relativefixedabsolutesticky元素可以使用的顶部,底部,左侧和右侧属性定位。然而,这些属性无法工作,除非是先设定position属性。他们也有不同的工作方式,这取决于定位方法。 1、static…...

正则表达式与grep

基本正则表达式BRE集合 匹配字符匹配次数位置锚定 符号作用^尖角号&#xff0c;用于模式的最正常&#xff0c;如“^haha”&#xff0c;匹配以haha单词开头的行$美元符&#xff0c;用于模式的最右侧&#xff0c;如“haha$”&#xff0c;表示haha单词结尾的行^$组合符&#xff…...

开发必备的IDEA 插件!效率提升 50 倍!

日常开发中&#xff0c;面向百度编程的程序员&#xff0c;很多时候&#xff0c;你跟大佬级别的差距&#xff0c;可能不仅仅是知识面的差距&#xff0c;还有就是开发效率的差距。以下是我常用的几个IDEA插件&#xff0c;废话不多说&#xff0c;直接肝干货&#xff01; 1. Codot…...

aws eks 集群访问ecr仓库拉取镜像的认证逻辑

本文主要讨论三个问题 ecr帮助程序在docker上如何配置eks集群访问ecr仓库的逻辑kubelet授权ecr的源码分析 ecr帮助程序 在docker环境下&#xff0c;可以通过在$HOME/.docker/config.json中指定凭证管理程序 docker login aws同样提供了证书助手&#xff0c;避免手动执行ecr认…...

Linux Socket Buffer介绍

一. 前言 Linux内核网络子系统的实现之所以灵活高效&#xff0c;主要是在于管理网络数据包的缓冲器-socket buffer设计得高效合理。在Linux网络子系统中&#xff0c;socket buffer是一个关键的数据结构&#xff0c;它代表一个数据包在内核中处理的整个生命周期。 二. Socket Bu…...

ACL与NAT

ACL---访问控制列表&#xff0c;是一种策略控制工具 功能&#xff1a;1.定义感兴趣流量&#xff08;数据层面 &#xff09; 2.定义感兴趣路由&#xff08;控制层面&#xff09; ACL 条目表项组成&#xff1a; 编号规则&#xff1a;步数或者跳数默认值为5&#xff0c;…...

使用gdb来debug程序并查找Segmentation fault原因

GDB 调试前言GDB基础用法1.启动及退出调试2.设置参数3.执行程序4.流程控制5.设置断点6.输出信息7.查看栈帧8.info命令9.显示源码GDB调试coredump文件关注公众号【程序员DeRozan】&#xff0c;回复【1207】&#xff0c;免费获取计算机经典资料及现金红包 前言 在开发程序时&…...

vbs简单语法及简单案例

文章目录一、简单语法1、变量2、输入3、输出4、选择语句5、循环二、用记事本编译中文乱码问题三、制作一个简单vbs脚本表白一、简单语法 1、变量 语法&#xff1a; dim 变量名例&#xff1a; dim a,b a1 b2 msgbox ab运行&#xff1a; 2、输入 语法&#xff1a;InputBox(…...

学板绘课程学费一般多少钱

学板绘课程学费一般多少钱&#xff1f;培训机构的费用和师资、模式有关&#xff0c;价格贵不贵要结合相同类型的机构多多对比。因为好些平台做了很多的宣传广告&#xff0c;运营成本很高&#xff0c; 终羊毛出在羊身上&#xff0c;这样的机构知名度很高&#xff0c;但是性价比不…...

48.在ROS中实现local planner(1)- 实现一个可以用的模板

有了之前45.在ROS中实现global planner&#xff08;1&#xff09;- 实现一个可以用模板的global planner的经验, 现在再去创建一个local planner的包就容易多了 1. 创建包 创建 cd ~/pibot_ros/ros_ws/src # 这里可以使用自己的ros workspace catkin_create_pkg sample_loc…...

jenkins基础部署

一、jenkins是什么1.Jenkins的前身是Hudson&#xff0c;采用JAVA编写的持续集成开源工具。Hudson由Sun公司在2004年启动&#xff0c;第一个版本于2005年在java.net发布。2007年开始Hudson逐渐取代CruiseControl和其他的开源构建工具的江湖地位。在2008年的JavaOne大会上在开发者…...

Unity3D -知识点(1)

1.场景视图鼠标滚轮&#xff1a;场景放大缩小鼠标右键&#xff1a;场景左右平移场景编辑器中&#xff0c;能看到什么&#xff1f;网格&#xff0c;每一格大小为1unit&#xff0c;建模不同&#xff0c;规定不同&#xff0c;(对应屏幕上100个像素)世界坐标系y轴向上为正x轴向右为…...

【学习笔记】NOIP暴零赛3

博弈(game) 观察到博弈过程中胜负态不会发生改变&#xff0c;那么求出从每个棋子出发能走的最长链&#xff0c;然后背包即可。 复杂度O(nm)O(nm)O(nm)。 #include<bits/stdc.h> #define ll long long #define pb push_back using namespace std; const int mod9982443…...

Java JSR规范列表

Java JSR规范列表目录概述需求&#xff1a;设计思路实现思路分析1.JSR2.JSR方法3.web service4.Webservice:5.数据处理器拓展实现参考资料和推荐阅读Survive by day and develop by night. talk for import biz , show your perfect code,full busy&#xff0c;skip hardness,m…...

Java必备小知识点1

Java程序类型: Applications和AppletApplications:是指在计算机操作系统中运行的程序。是完整的程序&#xff0c;能独立运行。被编译后&#xff0c;用普通的Java解释器就可以使其边解释边执行。必定含有一个main方法&#xff0c;程序执行时&#xff0c;首先寻找main方法&#x…...

JavaScript作用域、闭包

文章目录作用域、作用域链作用域作用域链循环中的作用域自由变量、闭包自由变量闭包的定义、表现、应用如何确定在闭包中获取正确的变量总结作用域、作用域链 作用域 编程语言中存储、访问、修改变量当中的值是一项基本能力、存储变量、访问变量必须按照一定的规则&#xff0…...

JavaScript Date(日期) 对象

JavaScript Date 对象是 JavaScript 中用于处理日期和时间的内置对象。它可以用于获取当前时间、设置日期和时间、计算日期和时间之间的差异、以及将日期和时间格式化为各种字符串格式。在本文中&#xff0c;我们将详细介绍 JavaScript Date 对象的作用和在实际工作中的用途。 …...

rust过程宏 proc-macro-workshop解题-4-sorted

名字版本号rust1.69.0OSubuntu 22.04这一大关卡介绍的是属性式过程宏。 第一关:01-parse-enum 还是简单的看我们是否已经实现了一个属性式过程宏的空架子,如果有这个空架子,就直接通过了。 use proc_macro::TokenStream; use proc_macro2; use syn;#[proc_macro_attribut…...

数据结构与算法—队列

队列 队列介绍 有序列表&#xff0c;可以用数组或者链表实现。遵循先进先出原则。 数组实现队列 public class ArrayQueue {public static void main(String[] args) {ArrayQueue queue new ArrayQueue(3);// 接收用户输入char key ;Scanner sc new Scanner(System.in);…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...