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

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...