首页 > 代码库 > BZOJ1441: Min
BZOJ1441: Min
1441: Min
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 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
4059 -1782
Sample Output
99
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.
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。