Steven_MengのBlog

传送门
巨佬zyd出的一道题

裴蜀定理:对于正整数$a,b$,方程$ax+by=c$有解的充分必要条件为$gcd(a,b)|c$

我们设$gcd(a,b)=d$,$\fr\dfracd = a′$,$\frac\dfrac= b′$,$\frac{c\dfracc′$
首先证明充分条件:
若$gcd(a,b)|c$则$c′$为整数,
原方程两边同时除以$d$,方程化为:$a′x+b′y=c′$,即$a′x=c′ \pmod {b′}$,
显然$a′,b′$两两互质,根据extgcd,我们知道这个方程一定有整数解。
充分性得证

再证明必要条件:
用反证法
若$gcd(a,b)不整除c$则$c’$不为整数,
原方程两边同时除以$d$,方程化为:$a′x+b′y=c′$,
等式左边为整数,右边不为整数,所以无解。
必要性得证


回到本题,发现这是一种裴蜀定理推广到$n$个数的情况
即$a_1x_1+a_2x_2+a_3x_3…a_nx_n=b$有解的充分必要条件为$gcd(a_1,a_2,a_3…a_n)|b$
又因为$b$为正整数,所以$b_{min}=gcd(a_1,a_2,a_3…a_n)$

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
inline int read(){//这个read自动忽略负数
int x=0;
char ch=getchar();
while (ch<'0'||ch>'9'){
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x;
}
int gcd(int jzm,int xjp){
return jzm%xjp==0?xjp:gcd(xjp,jzm%xjp);
}
int main(){
int n=read();
int ans=read();
for (register int i=2;i<=n;++i){
ans=gcd(ans,read());
}
printf("%d\n",ans);
}

 评论