裴蜀定理（或贝祖定理，Bézout‘s identity）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约
数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且（a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。
——百度百科
用人话来说就是：
$\sum{a_i \times x_i} = b $
上面的x有解当且仅当 $gcd(a_i)|b$
//Luogu P4549 【模板】裴蜀定理 //Nov,9th,2018 //裴蜀定理模板提 #include<iostream> #include<cstdio> using namespace std; long long read() { long long x=0,f=1; char c=getchar(); while(!isdigit(c)){if(c==‘-‘) f=-1;c=getchar();} while(isdigit(c)){x=x*10+c-‘0‘;c=getchar();} return x*f; } int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } int main() { int n=read(); int ans; if(n<2) ans=read(); else { ans=gcd(read(),read()); for(int i=3;i<=n;i++) ans=gcd(ans,read()); } printf("%d",ans>0?ans:-ans); return 0; }
原文：https://www.cnblogs.com/GoldenPotato/p/9934409.html
