首页 > 其他 > 详细

BZOJ1441: Min

时间:2014-08-12 00:33:23      阅读:339      评论:0      收藏:0      [点我收藏+]

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

99

HINT

 

Source

题解:

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

代码:

bubuko.com,布布扣
 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

 

BZOJ1441: Min,布布扣,bubuko.com

BZOJ1441: Min

原文:http://www.cnblogs.com/zyfzyf/p/3906050.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!