裴蜀定理及其证明
一、裴蜀定理
对于 \(x,y\) 的二元一次不定方程 \(ax+by=c\) ,其有解的充要条件为 \(\gcd(a,b)\mid c\) 。
1.充分性证明
充分性 若 \(\gcd(a,b)\mid c\) ,则 \(ax+by=c\) 有解。
证明
设 \(k\) 为 \(a,b\) 线性组合的最小非负解。令 \(q=\left\lfloor\dfrac{a}{k}\right\rfloor\) ,则有 \[ \begin{aligned} r&= a-qk = a-q(ax+by) \\[6pt]&=a(1-qx)+b(-qy) \end{aligned} \] 显然 \(r\) 也为 \(a,b\) 线性组合的解,且 \(0\le r \le k\) 。
由于 \(k\) 为最小非负解,故 \(r = 0\) ,那么 \(k \mid a\) 。同理可得 \(k\mid b\) 。
令 \(d=\gcd(a,b)\) ,则 \(k\mid d\) 且 \(d \ge k\) 。
因为 \(d\mid a,d\mid b\) 且 \(s\) 为 \(a,b\) 线性组合的解,所以 \(d \mid k\) 。
因为 \(s > 0\) ,所以 \(d = k\) ,则 \(ax+by=c\) 的最小非负解为 \(\gcd(a,b)\) 。
2.必要性证明
必要性 若 \(ax+by=c\) 有解,则 \(\gcd(a,b)\mid c\) 。
证明 令 \(d=\gcd(a,b)\) ,则 \(d\mid a,d\mid b\) 。
3.推广
对于不定方程 \(x_1y_1+x_2y_2+...+x_ny_n=k~(y_i \in \mathbb{Z})\) ,其有解的充要条件为 \(\gcd\{x_i\}\mid k\) 。
二、裴蜀定理模板题
题目链接:P4549 【模板】裴蜀定理
要注意负数要转成正数再算 \(\gcd\) 。
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define R register
int n,ans,a[25];
int gcd(R int a,R int b) {return b==0?a:gcd(b,a%b);}
signed main()
{
scanf("%lld",&n);
for(R int i=1; i<=n; i++)
{
scanf("%lld",&a[i]);
a[i]=a[i]>0?a[i]:-a[i];
ans=gcd((i==1?a[1]:ans),a[i]);
}
printf("%lld\n",ans);
return 0;
}