裴蜀定理 ★★☆☆☆

裴蜀定理（贝祖定理，Bézout's Theorem）刻画了整系数不定方程 ax + by 的取值与 gcd(a, b) 之间的关系，是判断不定方程是否有整数解的基础定理。本文给出定理、证明与推论，并附相关例题。

Tips：部分内容由 AI 生成，如发现问题请在评论区留言。

一、裴蜀定理

如果 a, b 是不全为 0 的整数，一定存在整数 x, y，满足

ax + by = gcd(a, b)

特别地，若 a, b 互质（即 gcd(a, b) = 1），则 ax + by = 1 必有整数解。

等价表述（集合形式）：当 x, y 取遍整数时，ax + by 所能取得的最小正值为 gcd(a, b)；即集合 { ax + by | ax + by > 0, x, y ∈ ℤ } 非空，且其中的最小正元素就是 gcd(a, b)。换句话说，ax + by 能取到的值恰好是 gcd(a, b) 的所有整数倍。

证明：设 x₀, y₀ 使 ax + by 取到最小正值，记这个值为 s，即 ax₀ + by₀ = s。

因为 gcd(a, b) | ax₀ 且 gcd(a, b) | by₀，所以 gcd(a, b) | s。

设 a = qs + r（0 ≤ r < s），则

r = a - qs = a - q(ax₀ + by₀) = a(1 - qx₀) + b(-qy₀)

说明 r 也能写成 ax + by 的形式。而 s 已是这种形式下的最小正值，且 r < s，故只能有 r = 0，即 s | a。同理 s | b，于是 s | gcd(a, b)。

既证得 gcd(a, b) | s 又证得 s | gcd(a, b)，故 s = gcd(a, b)。

二、推论

推论 1（方程可解性）：一定存在整数 x, y，满足 ax + by = gcd(a, b) · n（n 为任意整数）。反过来，方程 ax + by = c 有整数解当且仅当 gcd(a, b) | c。

推论 2（多个整数）：一定存在整数 x₁, x₂, …, xₙ，满足

a₁x₁ + a₂x₂ + ⋯ + aₙxₙ = gcd(a₁, a₂, …, aₙ)

三、例题

1. P4549 【模板】裴蜀定理

解题思路

即推论 2，答案为所有系数的最大公约数。注意系数可能为负，求 gcd 时应代入绝对值，确保结果为正。

时间复杂度 O(n log a)。

参考代码

#include <bits/stdc++.h>using namespace std;#define ll long longll n,a,ans=0;ll gcd (ll a, ll b){if (!b) return a;return gcd(b, a%b);}int main(){  cin.tie(0)->ios::sync_with_stdio(false);  cin>>n;while (n--) {    cin>>a;    a=abs(a);if (!a) continue;if (!ans) ans=a;else ans=gcd(ans,a);  }  cout<<ans;return 0;}

2. P2520 [HAOI2011] 向量

解题思路

8 个向量本质只有 4 种：(a, b), (b, a), (a, -b), (b, -a)。设使用次数分别为 k, q, w, c，则有

x = (k + w)·a + (q + c)·by = (k - w)·b + (q - c)·a

令 f = k + w, g = k - w, h = q + c, i = q - c。由 k = (f + g) / 2 等可知，f, g 必须同奇偶，h, i 也必须同奇偶。结合裴蜀定理（需 gcd(a, b) 整除 x, y），令 d = 2·gcd(a, b)，按 f, g 与 h, i 的奇偶分 4 种情况判定：

• 偶 / 偶：d | x 且 d | y
• 偶 / 奇：d | (x + b) 且 d | (y + a)
• 奇 / 偶：d | (x + a) 且 d | (y + b)
• 奇 / 奇：d | (x + a + b) 且 d | (y + a + b)

满足任意一种即可达，输出 Y，否则输出 N。

参考代码

#include <bits/stdc++.h>using namespace std;#define ll long longll t, a,b,x,y, g;ll gcd (ll a, ll b){if (!b) return a;return gcd(b, a%b);}bool check (ll x, ll y){return (x%g==0 && y%g==0);}int main(){  cin.tie(0)->ios::sync_with_stdio(false);  cin>>t;while (t--) {    cin>>a>>b>>x>>y;    a=llabs(a), b=llabs(b), x=llabs(x), y=llabs(y);    g = gcd(a,b)*2;if(check(x,y)||check(x+a,y+b)||check(x+b,y+a)||check(x+a+b,y+a+b)) cout << "Y\n";else cout<<"N\n";  }return 0;}

四、总结

• 裴蜀定理：ax + by 的最小正取值为 gcd(a, b)，且恰能取到 gcd 的所有整数倍。
• 有解条件：ax + by = c 有整数解 ⟺ gcd(a, b) | c。
• 多个整数：a₁x₁ + ⋯ + aₙxₙ 的最小正取值为 gcd(a₁, …, aₙ)。
• 常见应用：判断不定方程是否有解、判断线性组合能否凑出某数、判断向量是否可达。