BZOJ1441: Min

1441: Min

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 247 Solved: 153
[Submit][Status]

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

题解：

如果两个数的最大公约数是1,那么他们可以凑成任意一个正整数,如果gcd是2的话只能凑成2的倍数,所以ans=gcd(a_i)……

代码：

 1 var i,n,x,ans:longint;
 2 function gcd(x,y:longint):longint;
 3  begin
 4    if y=0 then exit(x) else exit(gcd(y,x mod y));
 5  end;
 6 
 7 begin
 8   assign(input,'input.txt');assign(output,'output.txt');
 9   reset(input);rewrite(output);
10   readln(n);read(ans);
11   for i:=2 to n do begin read(x);ans:=gcd(ans,abs(x));end;
12   writeln(ans);
13   close(input);close(output);
14 end.

View Code