江苏龙网

  1. 首页 > 生活 > >

扩展欧几里得算法：可以找到一组关于ax+by=gcd(a,b)的整数解，但是这个算法解出的|x|+|y|为啥是最小的

不见得是最小的。不信你自己捏两组数据试（建议写程序试）。我蠢了……今天闲来无事想给你举一个反例的，结果程序随机生成几十万组数据没找到反例……然后又看了一遍POJ 2142，那个题右边不一定是gcd(a, b)，可能是gcd(a, b)的倍数，所以才有反例。比如要用180和150组合出150，可以先用拓展欧几里得算出180*1 + 150 *(-1) = 30，然后两边同乘150/30 = 5，得到180*5 + 150*(-5) = 150,。可是x=5, y=-5显然不是最小的（实际上180*0 + 150*1 = 150最优）。根据wiki的说法：Extended Euclidean algorithmhttp://en.wikipedia.org/wiki/B%C3%A9zout\u0026#39;拓展欧几里得返回的是绝对值最小的两组之一，所以不一定是绝对值和最小的吧。我再生成一些数据测测看。找到了系数绝对值最小的证明：elementary number theory跑了一下实验，在a, b都小于10w的时候没发现反例TAT~#include \u0026lt;iostream\u0026gt;#include \u0026lt;cstdio\u0026gt;#include \u0026lt;cstdlib\u0026gt;#include \u0026lt;ctime\u0026gt;#include \u0026lt;cmath\u0026gt;#define MAXN 100000using namespace std;//扩展欧几里德算法int ExGCD(int a, int b, int\u0026amp; x, int\u0026amp; y){\tif(b == 0)\t{\t\tx = 1, y = 0;\t\treturn a;\t}\tint d = ExGCD(b, a%b, x, y);\tint temp = x;\tx = y;\ty = temp - a/b*y;\treturn d;}int main(){\tint x, y, d;\tfor (int a=2; a\u0026lt;MAXN; a++) for (int b=2; b\u0026lt;MAXN; b++) { d = ExGCD(a, b, x, y); int b1 = b/d, a1 = a/d; int x_ = x, y_ = y; if ( abs(x_)+abs(y_)\u0026gt;abs(x+b1)+abs(y-a1) ) { x_ = x+b1; y_ = y-a1; } if ( abs(x_)+abs(y_)\u0026gt;abs(x-b1)+abs(y+a1) ) { x_ = x-b1; y_ = y+a1; } if (x!=x_ || y!=y_) { printf("%d * %d + %d * %d = %d\", a, x, b, y, d); printf("%d * %d + %d * %d = %d\", a, x_, b, y_, d); system("pause"); } }\treturn 0;}
■网友
你可以假设它不是最小的，然后可以证明这个算法还可以继续


    推荐阅读


    上一篇：CUDA 异构编程和MPI并行机制应该怎样研究这两者之间应该咋结合

    下一篇：通过 iOS 设备的耳机口通信，进行配套硬件的开发，在通信协议的实现上有啥参考方法