[BZOJ1441] Min

题目

题目链接 需要权限
题目大意为给 n 个数 a_1, a_2, a_3 ... a_n 求一组整数序列 x_1, x_2, x_3...x_n 使得 S =\sum_{i=1}^{n} x_i*a_i, 求 S 的最小正整数解。

 

解题思路

裴蜀定理d_2 = xa_1 + ya_2 的最小正整数解为 \gcd(a_1, a_2), d_3 = xd_2 + ya_3 的最小正整数解为 \gcd(d_2, a_3), d_i = xd_{i-1} + ya_i 的最小正整数解为 \gcd(d_{i-1}, a_i).则d = d_n = gcd(gcd(gcd(...gcd(a_1, a_2), a_3 ...), a_{n-1}), a_n). 即 \gcd(a_1, a_2,...a_n).
所以最后答案即为所有数的最大公因数。

 

代码

 

完结

参考黄学长博客

One thought on “[BZOJ1441] Min

  1. Pingback: [BZOJ2257] [JSOI2009] 瓶子和燃料 | 火药

发表评论

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