作者netsphere ()
看板Prob_Solve
标题Re: [问题] 有关於欧基里德扩展演算法
时间Sat Aug 14 13:05:08 2010
※ 引述《linkone (小豆豆)》之铭言：
: 给定一个方程式 ax+by=d 其中 d为 a,b 的最大公因数
: 要求出 |x|+|y| 的最小值...
: 上网看了很多的推导过程都看不太懂.....
: 只知道要用欧基里德求公因数的递回观念
: 不知道有无较简洁的解释方法?
: 麻烦各位了
我也有一个类似的问题想问
给定一个方程式 ax+by=d a,b,d为任意整数
要求出 |x|+|y| 的最小值 或 显示无解
看起来没办法用扩充欧基里德的方式
有什麽比较好得方式来解呢？
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 123.205.55.104
※ 编辑: netsphere 来自: 123.205.55.104 (08/14 13:05)
1F：推 scwg:Extended Euclidean Algorithm 本来就可以知道是不是无解啊.. 08/15 05:23
2F：推 yzugsr:为什麽会无解? 没说x,y一定要是整数 08/15 14:27
3F：→ yzugsr:这不就是条直线吗? 08/15 14:27
4F：→ kytu:恩...原PO的意思应该是x,y隶属於整数 08/15 18:31
5F：→ kytu:也就是不定方程式有整数解。 08/15 18:42
6F：推 suhorng:一直搞不懂的是|x|+|y|最小, 之前没找到证明Orz 08/15 19:10