BZOJ 1441

1441: Min

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 467 Solved: 312
[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

HINT

Source

题解：

先把问题简单化，取n=2 取s=x1*a1+x2*a2>0最小这个方程和我们之前讲的线性不定方程形式相同。形如ax+by=c的方程有个特点，如果x,y有整数解的话，必须满足： gcd(a,b)|c 反过来，ax+by的正数最小值是gcd(a,b)

当推广到n>2的情况，上面的结论也是成立的。对于S=A1*X1+...An*Xn，它的正数最小值等于gcd(A1,A2,…,An) 证明方法和我们证明ax+by=c对该结论成立的方法类似。最后我们只需要求一下A1…An的gcd即可。

AC代码：

#include<cstdio>
#include<cstdlib>
using namespace std;
int n,a[1000010];
int gcd(int a,int b){
    return !b?a:gcd(b,a%b);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=2;i<=n;i++) a[i]=gcd(a[i],a[i-1]);
    printf("%d
",abs(a[n]));
    return 0;
}