首页 > 代码库 > 算法学习——讲一个大家可能都知道的东西

算法学习——讲一个大家可能都知道的东西

bzoj1441

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
乍一看,感觉不会。
再一看,(*@ο@*) 哇~不会
看题解,才知道是裴蜀定理。
什么是裴蜀定理呢

技术分享,技术分享(|指能整除)

证明喵。。

比如说只有两个数a和b,x1=x,x2=y.

技术分享

那么

技术分享

证毕

是不是超simple

那么。。这题不就是求d吗。。

裴蜀定理是不是超神奇!

PS:谁知道如何快速补八下科学啊T_T,期末考快到了啊。。

算法学习——讲一个大家可能都知道的东西