BZOJ 1441 裴蜀定理

思路：

若a,b是整数,且（a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。

它的一个重要推论是：a,b互质的充要条件是存在整数x,y使ax+by=1.

设a1,a2,a3......an为n个整数，d是它们的最大公约数，那么存在整数x1......xn使得x1*a1+x2*a2+...xn*an=d。

特别来说，如果a1...an互质（不是两两互质），那么存在整数x1......xn使得x1*a1+x2*a2+...xn*an=1。证法类似两个数的情况。

from 百度

//By SiriusRen

#include <cstdio>

using namespace std;

int n,ans,xx;

int gcd(int x,int y){return y?gcd(y,x%y):x;}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&xx),ans=gcd(ans,xx);

    printf("%d\n",ans>?ans:-ans);

}

巴特西

BZOJ 1441 裴蜀定理

最新文章

热门文章