BZOJ 1441: Min(裴蜀定理)

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

如果题目要求一组非负整数解,那么就是之前一种转成最短路问题的做法了。但是这个题目说得是整数解,那么直接用裴蜀定理就好了。
裴蜀定理就是:对于整系数方程ax+by=m,设g=(a,b),方程有整数解当且仅当g|m。可以拓展到n元形式。所以这个题就是求个gcd就没了。。。

发表评论

电子邮件地址不会被公开。 必填项已用*标注