Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 320 Solved: 213
给出n个数(A1...An)现求一组整数序列(X1...Xn)使得S=A1*X1+...An*Xn>0,且S的值最小
第一行给出数字N,代表有N个数 下面一行给出N个数
S的最小值
2 4059 -1782
99
题解:今天才知道有个很神奇的东西叫做裴蜀定理= =
比如此题中(详见 百度百科——裴蜀定理)
1 /**************************************************************
2 Problem: 1441
3 User: HansBug
4 Language: Pascal
5 Result: Accepted
6 Time:0 ms
7 Memory:224 kb
8 ****************************************************************/
9
10 var
11 i,j,k,l,m,n:longint;
12 function gcd(x,y:longint):longint;
13 var z:longint;
14 begin
15 x:=abs(x);y:=abs(y);
16 while y<>0 do
17 begin
18 z:=x mod y;
19 x:=y;
20 y:=z;
21 end;
22 exit(x);
23 end;
24 begin
25 readln(n);
26 read(m);
27 if n=1 then
28 begin
29 readln;
30 writeln(m);
31 readln;
32 halt;
33 end;
34 for i:=2 to n do
35 begin
36 read(j);
37 m:=gcd(m,j);
38 end;
39 readln;
40 writeln(m);
41 readln;
42 end.