[Time Gate]
https://www.luogu.org/problemnew/show/P4549
【解题思路】
数论+最大公约数+不定方程
裴蜀定理内容及简要证明
ax+by=c（xy为任意整数）成立的充要条件是c是gcd（a,b）的倍数
设s=gcd?(a,b)，显然s∣a，并且s∣b
又因为x,y∈Z∗
所以s∣ax,s∣by
显然要使得之前的式子成立，则必须满足c是a和b的公约数的倍数
又因为x和y是正整数
所以c必然是a,b,最大公约数
因此，证得该定理成立
多个数即可同理
【code】
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 using namespace std; 5 int n,k,ans; 6 inline int gcd(int a,int b){ 7 if(b==0)return a; 8 return gcd(b,a%b); 9 } 10 int main(){ 11 //freopen("4549.in","r",stdin); 12 //freopen("4549.out","w",stdout); 13 scanf("%d",&n); 14 for(register int i=1;i<=n;i++){ 15 scanf("%d",&k); 16 if(k<0)k*=(-1); 17 ans= gcd(ans,k); 18 } 19 printf("%d\n",ans); 20 return 0; 21 }
原文：https://www.cnblogs.com/66dzb/p/11166288.html