bzoj 1441: Min （gcd+裴蜀定理）

1441: Min

Time Limit: 5 Sec   Memory Limit: 64 MB Submit: 520   Solved: 342 [ Submit][ Status][ Discuss]

Description

给出n个数(A1...An)现求一组整数序列(X1...Xn)使得S=A1*X1+...An*Xn>0,且S的值最小

Input

第一行给出数字N,代表有N个数 下面一行给出N个数

Output

S的最小值

Sample Input

2 4059 -1782

Sample Output

99

HINT

Source

[ Submit][ Status][ Discuss] 

题解：gcd+裴蜀定理

gcd(a,b)就是最小的可以表示成ax+b*y的正整数。

所以我们直接对于所有读入的a求gcd即可

因为x,y的正负是不确定的，所有完全可以用x,y来实现a,b的正负，所以直接忽略a的符号即可。

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; int n; int gcd(int x,int y) { int r; while (y) { r=x%y; x=y; y=r; } return x; } int main() { freopen("a.in","r",stdin); scanf("%d",&n); int a1,a2; scanf("%d",&a1); if (a1<0) a1=-a1; for (int i=2;i<=n;i++){ scanf("%d",&a2); if (a2<0) a2=-a2; a1=gcd(a1,a2); } printf("%d\n",a1); }