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

ACM数论裴蜀定理（贝祖定理）

news 文章来源：https://blog.csdn.net/qq_40772692/article/details/129099553 2024/11/2 12:26:02

一.内容定义

「裴蜀定理」，又称贝祖定理（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;}
};

$nums_1,nums_2,....,nums_n$