大概意思 给定 a b k找到满足ax+by=k 的x，y 令|x|+|y|最小（等时令a|x|+b|y|最小）不妨a 〉b

先用扩展欧几里得算法求出 一组解 x0，y0

通解可以表示为x=x0+b/d *t  y=y0-a/d *t

|x|+|y|=|x0+b/d *t |+|y0-a/d *t| 简单分析一下可知这个关于t的函数的最小值应该在t零点附近（因为要求t为整数）取到，再进一步考虑知道在   y0*d/a 附近的两整点里取。故直接验证这两点即可。

http://hi.baidu.com/5l2%5F/blog/item/a0381951b5738a1e367abef0.html

• Re:强大。 终于想通为什么最小值在t零点了 Orz (0) arena_zp 2008-11-03 20:18:01
• 妙啊！ (113) swust20064469 2009-07-14 10:40:45
  • Re:妙啊！ (141) guowentian 2013-08-13 09:51:55
  • Re:妙啊！ (119) xz_lj 2020-02-23 10:19:43
• Re:思路~ (379) zhengzhenzhe220 2010-07-21 21:05:01