U77080 大水题 裴蜀定理

传送门
巨佬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);
}