大家好,欢迎来到IT知识分享网。
前言
原来裴蜀是法国数学家QwQ
一、裴蜀定理
对于 x , y x,y x,y 的二元一次不定方程 a x + b y = c ax+by=c ax+by=c ,其有解的充要条件为 gcd ( a , b ) ∣ c \gcd(a,b)\mid c gcd(a,b)∣c
1.充分性证明
充分性:若 gcd ( a , b ) ∣ c \gcd(a,b)\mid c gcd(a,b)∣c ,则 a x + b y = c ax+by=c ax+by=c 有解
设 k k k 为 a , b a,b a,b 线性组合的最小非负解
令 q = ⌊ a k ⌋ q=\left\lfloor\dfrac{a}{k}\right\rfloor q=⌊ka⌋ ,则有 r = a m o d k = a − q k = a − q ( a x + b y ) = a ( 1 − q x ) + b ( − q y ) r=a \mod k = a-qk = a-q(ax+by) = a(1-qx)+b(-qy) r=amodk=a−qk=a−q(ax+by)=a(1−qx)+b(−qy)
显然 r r r 也为 a , b a,b a,b 线性组合的解,且 0 ≤ r ≤ k 0\le r \le k 0≤r≤k
∵ k \because k ∵k 为最小非负解
∴ r = 0 \therefore r=0 ∴r=0
∴ k ∣ a \therefore k\mid a ∴k∣a
同理 k ∣ b k\mid b k∣b
令 d = gcd ( a , b ) d=\gcd(a,b) d=gcd(a,b) ,则 s ∣ d s\mid d s∣d 且 d ≥ s d \ge s d≥s
∵ d ∣ a , d ∣ b \because d\mid a,d\mid b ∵d∣a,d∣b 且 s s s 为 a , b a,b a,b 线性组合的解
∴ d ∣ s \therefore d\mid s ∴d∣s
∵ s > 0 \because s>0 ∵s>0
∴ d = s \therefore d=s ∴d=s
则 a x + b y = c ax+by=c ax+by=c 的最小非负解为 gcd ( a , b ) \gcd(a,b) gcd(a,b)
显然 ∀ c = k gcd ( a , b ) , k ∈ Z + \forall c=k\gcd(a,b),k\in \Z^+ ∀c=kgcd(a,b),k∈Z+ 是原方程的解
2.必要性证明
必要性:若 a x + b y = c ax+by=c ax+by=c 有解,则 gcd ( a , b ) ∣ c \gcd(a,b)\mid c gcd(a,b)∣c
证明:
令 d = gcd ( a , b ) d=\gcd(a,b) d=gcd(a,b) ,则 d ∣ a , d ∣ b d\mid a,d\mid b d∣a,d∣b
∵ a x + b y = c \because ax+by=c ∵ax+by=c 有解
∴ d ∣ a x , d ∣ b y \therefore d\mid ax,d\mid by ∴d∣ax,d∣by
∴ d ∣ a x + b y = c \therefore d\mid ax+by=c ∴d∣ax+by=c
3.推广
对于不定方程 x 1 y 1 + x 2 y 2 + . . . + x n y n = k , ∀ y i ∈ Z x_1y_1+x_2y_2+…+x_ny_n=k, \forall y_i \in \Z x1y1+x2y2+...+xnyn=k,∀yi∈Z ,其有解的充要条件为 gcd { x i } ∣ k \gcd\{x_i\}\mid k gcd{
xi}∣k
证明略
二、裴蜀定理模板题
题目链接:P4549 【模板】裴蜀定理
即推广结论裸题
要注意负数要转成正数再算 gcd \gcd 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;
}
IT知识分享网
总结
本文简单介绍了裴蜀定理
转载请说明出处
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/7544.html